Dynamic chromatic number of regular graphs ?
A k k -dynamic coloring of a graph G G is a proper coloring of G G with k k colors such that for every vertex v?V(G) v ? V ( G ) of degree at least 2, the neighbors of v v receive at least 2 colors. The dynamic chromatic number of a graph G G , ?2(G) ? 2 ( G ) , is the least number k k such that G G admits a k k -dynamic coloring. It was conjectured [B. Montgomery, Dynamic coloring of graphs, Ph.D. Thesis, West Virginia University, 2001.] that if G G is a k k -regular graph, then ?2(G)??(G)?2 ? 2 ( G ) ? ? ( G ) ? 2 . In this paper, we prove that if G G is a k k -regular graph with ?(G)?4 ? ( G ) ? 4 , then ?2(G)??(G)+?(G2) ? 2 ( G ) ? ? ( G ) + ? ( G 2 ) . It confirms the conjecture for all regular graphs with diameter at most 2 2 and chromatic number at least 4 4 . In fact, it shows that ?2(G)??(G)?1 ? 2 ( G ) ? ? ( G ) ? 1 provided that G G has diameter at most 2 2 and ?(G)?4 ? ( G ) ? 4 . Moreover, we show that for any k k -regular graph G G with no induced C4 C 4 , ?2(G)??(G)?2?4lnk+1? ? 2 ( G ) ? ? ( G ) ? 2 ? 4 ln k + 1 ? . Also, we show that for any n n there exists a regular graph G G whose chromatic number is n n and ?2(G)??(G)?1 ? 2 ( G ) ? ? ( G ) ? 1 . This result gives a negative answer to a conjecture of Ahadi etal. [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].
dynamic chromatic number 2-colorability of hypergraphs