Dynamic Chromatic Number of Regular Graphs

Abstract

A dynamic coloring of a graph $G$ is a proper coloring such that for every vertex $v\in V(G)$ of degree at least 2, the neighbors of $v$ receive at least 2 colors. It was conjectured [B. Montgomery. {\em Dynamic coloring of graphs}. PhD thesis, West Virginia University, 2001.] that if $G$ is a $k$-regular graph, then ${\chi }_2(G)-\chi (G)\le 2$. In this paper, we prove that if $G$ is a $k$-regular graph with $\chi (G)\ge 4$, then ${\chi }_2(G)\le \chi (G)+\alpha (G^2)$. It confirms the conjecture for all regular graph $G$ with diameter at most 2 and $\chi (G)\ge 4$. In fact, it shows that ${\chi }_2(G)-\chi (G)\le 1$ provided that $G$ has diameter at most 2 and $\chi (G)\ge 4$. Moreover, we show that for any $k$-regular graph $G$, ${\chi }_2(G)-\chi (G)\le 6\ln k+2$. Also, we show that for any $n$ there exists a regular graph $G$ whose chromatic number is $n$ and ${\chi }_2(G)-\chi (G)\ge 1$. This result gives a negative answer to a conjecture of [A. Ahadi, S. Akbari, A. Dehghan, and M. Ghanbari. \newblock On the difference between chromatic number and dynamic chromatic number of graphs. \newblock {\em Discrete Math.}, In press].

8 pages