Bounds on the Dynamic Chromatic Number of a Graph in Terms of its Chromatic Number

Abstract

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 χ(G) of a graph G, one can define its dynamic number χ_d(G) (the minimum number of colors in a dynamic coloring) and dynamic chromatic number χ₂(G) (the minimum number of colors in a proper dynamic coloring). We prove that χ₂(G) ≤ χ(G) · χ_d(G) and construct an infinite series of graphs for which this bound on χ₂(G) is tight.

For a graph G, set \( k=\left\lceil \frac{2\Delta (G)}{\delta (G)}\right\rceil \) We prove that χ₂(G) ≤ (k+1)c. Moreover, in the case where k ≥ 3 and Δ(G) ≥ 3, we prove the stronger bound χ₂(G) ≤ kc.