Dynamic Coloring and Graph Squares of Regular Graphs
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)\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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.09565
curl -X POST /api/v1/records/arxiv/2610.09565/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.09565/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'