PreprintCC BY 4.0arXiv
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 χrd(G). We study dynamic colorings of regular graphs. A straighforward observation shows that χrd(G)=χ(G2), for any r-regular graph G. We prove that χ3d(G)=χ(G2)≤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 Cp(1,3) for each r∈{2,3,4}. In particular, the case r=4 determines χ(C2p(1,3)).
Related
- Edge‐Coloring a Graph G so That Every Copy of a Graph H Has an Odd Color Class
- Bounds for B-coloring planar and outerplanar graphs
- COLORING SEMIMINIMAL CAYLEY GRAPHS
- Local-to-Global Theorems Based on Cones with Applications to Graph Coloring
- Double-Partition Coloring problem: a unified approach for conflict-free coloring of hypergraphs and other coloring problems in graphs
BibTeX
@misc{gutierrez2026dynamic,
title = {{Dynamic Coloring and Graph Squares of Regular Graphs}},
author = {Juan Gutierrez and Grover Ugarte},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.09565},
eprint = {2610.09565},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.09565},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Dynamic Coloring and Graph Squares of Regular Graphs
AU - Juan Gutierrez
AU - Grover Ugarte
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2610.09565
UR - https://arxiv.org/abs/2610.09565
AB - 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 χ_r^d(G). We study dynamic colorings of regular graphs. A straighforward observation shows that χ_r^d(G)=χ(G^2), for any r-regular graph G. We prove that χ_3^d(G)=χ(G^2)≤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∈{2,3,4}. In particular, the case r=4 determines χ(C^2_p(1,3)).
ER -