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=\left\lceil \frac{2\Delta (G)}{\delta (G)}\right\rceil \) 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
R. L. Brooks, “On coloring the nodes of a network,” Proc. Cambridge Philos. Soc., 37, 194–197 (1941).
H.-J. Lui, B. Montgomery, and H. Poon, “Upper bounds of dynamic chromatic number,” Ars Combin., 68, 193–201 (2003).
S. Akbari, M. Ghanbari, and S. Jahanbekam, “On the list dynamic coloring of graphs,” Discrete Appl. Math., 157, No. 14, 3005–3007 (2009).
S. Akbari, M. Ghanbari, and S. Jahanbekam, “On the dynamic chromatic number of graphs,” Contemp. Math., 531, 11–18 (2010).
D. V. Karpov, “Dynamic proper colorings of a graph,” Zap. Nauchn. Semin. POMI, 381, 47–77 (2010).
N. V. Gravin and D. V. Karpov, “On proper colorings of hypergraphs,” Zap. Nauchn. Semin. POMI, 391, 79–89 (2011).
D. Karpov, “An analog of Brooks’ theorem for dynamic colorings,” Moscow J. Combin. Number Theory, 6, No. 1 (2016).
A. Ahadi, S. Akbari, A. Dehghan, and M. Ghanbari, “On the difference between chromatic number and dynamic chromatic number of graphs,” Discrete Math., 312, No. 17, 2579–2583 (2012).
S.-J. Kim, S. J. Lee, and W.-J Park, “Dynamic coloring and list dynamic coloring of planar graphs,” Discrete Appl. Math., 161, 2207–2212 (2013).
Author information
Authors and Affiliations
Corresponding author
Additional information
Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 450, 2016, pp. 37–42.
Rights and permissions
About this article
Cite this article
Vlasova, N.Y., Karpov, D.V. Bounds on the Dynamic Chromatic Number of a Graph in Terms of its Chromatic Number. J Math Sci 232, 21–24 (2018). https://doi.org/10.1007/s10958-018-3855-4
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10958-018-3855-4