|
Zapiski Nauchnykh Seminarov POMI, 2016, Volume 450, Pages 37–42
(Mi znsl6335)
|
|
|
|
This article is cited in 2 scientific papers (total in 2 papers)
Bounds on the dynamic chromatic number of a graph in terms of the chromatic number
N. Y. Vlasovaa, D. V. Karpovba a St. Petersburg State University, St. Petersburg, Russia
b St. Petersburg Department of Steklov Mathematical Institute of Russian Academy of Sciences, St. Petersburg, Russia
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 $\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$.
Key words and phrases:
chromatic number, proper coloring, dynamic coloring.
Received: 11.10.2016
Citation:
N. Y. Vlasova, D. V. Karpov, “Bounds on the dynamic chromatic number of a graph in terms of the chromatic number”, Combinatorics and graph theory. Part VIII, Zap. Nauchn. Sem. POMI, 450, POMI, St. Petersburg, 2016, 37–42; J. Math. Sci. (N. Y.), 232:1 (2018), 21–24
Linking options:
https://www.mathnet.ru/eng/znsl6335 https://www.mathnet.ru/eng/znsl/v450/p37
|
Statistics & downloads: |
Abstract page: | 147 | Full-text PDF : | 39 | References: | 29 |
|