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

• Published in: Journal of mathematical sciences (New York, N.Y.) N.Y.), 2018-07, Vol.232 (1), p.21-24
• Main Authors: Vlasova, N. Y., Karpov, D. V.
• Format: Article
• Language: English
• Subjects: Graph coloring; Infinite series; Mathematics; Mathematics and Statistics
• ISSN: 1072-3374; 1573-8795
• DOI: 10.1007/s10958-018-3855-4

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 χ 2 (G) (the minimum number of colors in a proper dynamic coloring). We prove that χ 2 (G) ≤ χ(G) · χ d (G) and construct an infinite series of graphs for which this bound on χ 2 (G) is tight. For a graph G, set k = 2 Δ G δ G We prove that χ 2 (G) ≤ (k+1)c. Moreover, in the case where k ≥ 3 and Δ(G) ≥ 3, we prove the stronger bound χ 2 (G) ≤ kc.