Dynamic Coloring and Graph Squares of Regular Graphs
In the authors' words
An -dynamic coloring of a graph is a proper vertex coloring in which every vertex sees at least distinct colors in its neighborhood. The minimum number of colors in such a coloring is the -dynamic chromatic number . We study dynamic colorings of regular graphs. A straighforward observation shows that , for any -regular graph . We prove that for every claw-free cubic graph , and the bound is sharp. For Hamiltonian claw-free cubic graphs, we improve the bound to apart from four explicit exceptions. We also determine exactly the -dynamic chromatic number of the -regular circulant graph for each . In particular, the case determines .
Main resultLimitation the authors admit
Appeared: Thursday, October 8. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 15 pages