On r-dynamic coloring of some graph operations - Ika Hesti Agustin; D. Dafik; A. Y. Harsya (Indonesian Journal of Combinatorics, 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 \in 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)\le χ_{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.