Bounds on the dynamic chromatic number of a~graph in terms of the chromatic number

N. Y. Vlasova ; D. V. Karpov

Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part VIII, Tome 450 (2016), pp. 37-42

Résumé

A vertex coloring of a graph is called dynamic, if the neighborhood of any vertex of degree at least 2 contains at least two vertices of distinct colors. Similarly to the chromatic number $\chi(G)$ of the graph $G$ one can define its dynamic number $\chi_d(G)$ (the minimal number of colors in a dynamic coloring) and dynamic chromatic number $\chi_2(G)$ (the minimal number of colors in a proper dynamic coloring). We prove that $\chi_2(G)\le\chi(G)\cdot\chi_d(G)$ and construct an infinite series of graphs for which this bound on $\chi_2(G)$ is tight. For a graph $G$ set $k=\lceil\frac{2\Delta(G)}{\delta(G)}\rceil$. We prove that $\chi_2(G)\le (k+1)c$. Moreover, in the case where $k\ge3$ and $\Delta(G)\ge3$ we prove a stronger bound $\chi_2(G)\le kc$.