zbMATH — the first resource for mathematics

On the dynamic chromatic number of graphs. (English) Zbl 1232.05071
Brualdi, Richard A. (ed.) et al., Combinatorics and graphs. Selected papers based on the presentations at the 20th anniversary conference of IPM on combinatorics, Tehran, Iran, May 15–21, 2009. Dedicated to Reza Khosrovshahi on the occasion of his 70th birthday. Providence, RI: American Mathematical Society (AMS) (ISBN 978-0-8218-4865-4/pbk). Contemporary Mathematics 531, 11-18 (2010).
Summary: A proper vertex \(k\)-coloring of a graph \(G\) is called dynamic, if for every vertex \(v\) with degree at least 2, the neighbors of \(v\) receive at least two different colors. The smallest integer \(k\) such that \(G\) has a \(k\)-dynamic coloring is called the dynamic chromatic number of \(G\) and denoted by \(\chi_2(G)\). In this paper we study the dynamic chromatic number of graphs all of whose cycles have lengths divisible by \(\ell\), \(\ell\geq 2\).
Let \(G\) be a graph and \(\ell\geq 3\) be a natural number. We prove that if the length of every cycle of \(G\) is divisible by \(\ell\) and \(G\) has no component isomorphic to \(C_5\), then \(\chi_2(G) \leq 4\). Also, it is shown that for every \(k\)-regular bipartite graph \(G\) \((k\geq 4)\), there is a \(4\)-dynamic coloring of \(G\) using \(2\) colors in each part.
For the entire collection see [Zbl 1202.05003].

05C15 Coloring of graphs and hypergraphs
05C38 Paths and cycles