Dynamic chromatic number of regular graphs

A kk-dynamic coloring of a graph GG is a proper coloring of GG with kk colors such that for every vertex v∈V(G)v∈V(G) of degree at least 2, the neighbors of vv receive at least 2 colors. The dynamic chromatic number of a graph GG, χ2(G)χ2(G), is the least number kk such that GG admits a kk-dynamic coloring. It was conjectured [B. Montgomery, Dynamic coloring of graphs, Ph.D. Thesis, West Virginia University, 2001.] that if GG is a kk-regular graph, then χ2(G)−χ(G)≤2χ2(G)−χ(G)≤2. In this paper, we prove that if GG is a kk-regular graph with χ(G)≥4χ(G)≥4, then χ2(G)≤χ(G)+α(G2)χ2(G)≤χ(G)+α(G2). It confirms the conjecture for all regular graphs with diameter at most 22 and chromatic number at least 44. In fact, it shows that χ2(G)−χ(G)≤1χ2(G)−χ(G)≤1 provided that GG has diameter at most 22 and χ(G)≥4χ(G)≥4. Moreover, we show that for any kk-regular graph GG with no induced C4C4, χ2(G)−χ(G)≤2⌈4lnk+1⌉χ2(G)−χ(G)≤2⌈4lnk+1⌉. Also, we show that for any nn there exists a regular graph GG whose chromatic number is nn and χ2(G)−χ(G)≥1χ2(G)−χ(G)≥1. This result gives a negative answer to a conjecture of Ahadi et al. [A. Ahadi, S. Akbari, A. Dehghan, M. Ghanbari, On the difference between chromatic number and dynamic chromatic number of graphs, Discrete Math. Available online 2011].