Several classes of graphs and their r-dynamic chromatic numbers

Abstract

Let G be a simple, connected and undirected graph. Let r; k be natural numbers. By a proper k-coloring of a graph G, we mean a map c : V (G) ! S, where jSj = k, such that any two adjacent vertices receive di erent colors. An r-dynamic k-coloring is a proper k-coloring c of G such that jc(N(v))j minfr; d(v)g for each vertex v in V (G), where N(v) is the neighborhood of v and c(S) = fc(v) : v 2 Sg for a vertex subset S. The r-dynamic chromatic number, written as (G), is the minimum k such that G has an r-dynamic k-coloring. By simple observation it is easy to see that

r (G) r+1 (G), however r+1 (G) r r (G) does not always show a small di erence for any r. Thus, nding an exact value of (G) is signi cantly useful. In this paper, we will study some of them especially when G are prism graph, three-cyclical ladder graph, joint graph and circulant graph.