Dynamic Coloring and Graph Squares of Regular Graphs

Abstract

An $r$-dynamic coloring of a graph $G$ is a proper vertex coloring in which every vertex $v$ sees at least $\min\{r,d(v)\}$ distinct colors in its neighborhood. The minimum number of colors in such a coloring is the $r$-dynamic chromatic number $\chi_r^d(G)$. We study dynamic colorings of regular graphs. A straighforward observation shows that $\chi_r^d(G)=\chi(G^2)$, for any $r$-regular graph $G$. We prove that $\chi_3^d(G)=\chi(G^2)\le6$ for every claw-free cubic graph $G$, and the bound is sharp. For Hamiltonian claw-free cubic graphs, we improve the bound to $5$ apart from four explicit exceptions. We also determine exactly the $r$-dynamic chromatic number of the $4$-regular circulant graph $C_p(1,3)$ for each $r\in\{2,3,4\}$. In particular, the case $r=4$ determines $\chi(C^2_p(1,3))$.