Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
This paper investigates $r$-dynamic colorings of regular graphs, specifically focusing on the $r$-dynamic chromatic number $\chi_r(G)$, which is equivalent to the chromatic number of the graph squared ($\chi(G^2)$) for $r$-regular graphs. The authors prove that for claw-free cubic graphs, $\chi_3(G) \le 6$, and this bound is tight, with a further improvement to $5$ for Hamiltonian instances, barring a few exceptions. Additionally, the exact $r$-dynamic chromatic numbers are determined for a specific family of $4$-regular circulant graphs.
Claw-free cubic graphs can be 3-dynamically colored with at most 6 colors, a bound that is sharp and can be reduced to 5 for Hamiltonian cases.
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(G)$. We study dynamic colorings of regular graphs. A straighforward observation shows that $\chi_r(G)=\chi(G^2)$, for any $r$-regular graph $G$. We prove that $\chi_3(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))$.