Bounds on the Dynamic Chromatic Number of a Graph in Terms of its Chromatic Number
- Authors: Vlasova N.Y.1, Karpov D.V.2
-
Affiliations:
- St. Petersburg State University
- St. Petersburg Department of Steklov Institute of Mathematics and St. Petersburg State University
- Issue: Vol 232, No 1 (2018)
- Pages: 21-24
- Section: Article
- URL: https://journals.rcsi.science/1072-3374/article/view/241251
- DOI: https://doi.org/10.1007/s10958-018-3855-4
- ID: 241251
Cite item
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 χ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.
About the authors
N. Y. Vlasova
St. Petersburg State University
Author for correspondence.
Email: evropa2100@mail.ru
Russian Federation, St. Petersburg
D. V. Karpov
St. Petersburg Department of Steklov Institute of Mathematics and St. Petersburg State University
Email: evropa2100@mail.ru
Russian Federation, St. Petersburg