On r-dynamic coloring of some graph operations - Ika Hesti Agustin; D. Dafik; A. Y. Harsya (Indonesian Combinatorial Society (InaCombS), 2016)
Let G be a simple, connected and undirected graph. Let r,k be natural number. By a proper k-coloring of a graph G, we mean a map c : V (G) → S, where |S| = k, such that any two adjacent vertices receive different colors. An r-dynamic k-coloring is a proper k-coloring c of G such that |c(N (v))| ≥ min{r, d(v)} for each vertex v in V(G), where N (v) is the neighborhood of v and c(S) = {c(v) : v S} for a vertex subset S . The r-dynamic chromatic number, written as χ_r(G), is the minimum k such that G has an r-dynamic k-coloring. Note that the 1-dynamic chromatic number of graph is equal to its chromatic number, denoted by χ(G), and the 2-dynamic chromatic number of graph has been studied under the name a dynamic chromatic number, denoted by χ_d(G). By simple observation it is easy to see that χ_r(G)χ_r+1(G), however χ_r+1(G)-χ_r(G) can be arbitrarily large, for example χ(Petersen)=2, χ_d(Petersen)=3, but χ_3(Petersen)=10. Thus, finding an exact values of χ_r(G) is significantly useful. In this paper, we will show some exact values of χ_r(G) when G is an operation of special graphs.