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)\le 6$ 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_p^2(1,3))$.

15 pages; Changed notation χ_r to χ_r^d; Fixed typo χ_d