Geodesic
Bounds on the dynamic chromatic number of a graph in terms of the chromatic number
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part VIII, Tome 450 (2016), pp. 37-42
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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$. 
@article{ZNSL_2016_450_a2,
     author = {N. Y. Vlasova and D. V. Karpov},
     title = {Bounds on the dynamic chromatic number of a~graph in terms of the chromatic number},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {37--42},
     year = {2016},
     volume = {450},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2016_450_a2/}
}
TY  - JOUR
AU  - N. Y. Vlasova
AU  - D. V. Karpov
TI  - Bounds on the dynamic chromatic number of a graph in terms of the chromatic number
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2016
SP  - 37
EP  - 42
VL  - 450
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2016_450_a2/
LA  - ru
ID  - ZNSL_2016_450_a2
ER  - 
%0 Journal Article
%A N. Y. Vlasova
%A D. V. Karpov
%T Bounds on the dynamic chromatic number of a graph in terms of the chromatic number
%J Zapiski Nauchnykh Seminarov POMI
%D 2016
%P 37-42
%V 450
%U http://geodesic.mathdoc.fr/item/ZNSL_2016_450_a2/
%G ru
%F ZNSL_2016_450_a2
N. Y. Vlasova; D. V. Karpov. Bounds on the dynamic chromatic number of a graph in terms of the chromatic number. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part VIII, Tome 450 (2016), pp. 37-42. http://geodesic.mathdoc.fr/item/ZNSL_2016_450_a2/

[1] R. L. Brooks, “On coloring the nodes of network”, Proc. Cambridge Philos. Soc., 37 (1941), 194–197 | DOI | MR | Zbl

[2] H.-J. Lui, B. Montgomery, H. Poon, “Upper bounds of dynamic chromatic number”, Ars Combinatoria, 68 (2003), 193–201 | MR

[3] S. Akbari, M. Ghanbari, S. Jahanbekam, “On the list dynamic coloring of graphs”, Discrete Applied Mathematics, 157:14 (2009), 3005–3007 | DOI | MR | Zbl

[4] S. Akbari, M. Ghanbari, S. Jahanbekam, “On the Dynamic Chromatic Number of Graphs”, Contemp. Math., 531 (2010), 11–18 | DOI | MR | Zbl

[5] D. V. Karpov, “Dinamicheskie pravilnye raskraski grafov”, Zap. nauchn. semin. POMI, 381, 2010, 47–77

[6] N. V. Gravin, D. V. Karpov, “O pravilnykh raskraskakh gipergrafov”, Zap. nauchn. semin. POMI, 391, 2011, 79–89

[7] D. Karpov, “An Analog of Brooks' Theorem for Dynamic Colorings”, Moscow J. Combinat. Number Theory, 6:1 (2016), 25–63 | MR

[8] A. Ahadi, S. Akbari, A. Dehghan, M. Ghanbari, “On the difference between chromatic number and dynamic chromatic number of graphs”, Discrete Math., 312:17 (2012), 2579–2583 | DOI | MR | Zbl

[9] S.-J. Kim, S. J. Lee, W.-J. Park, “Dynamic coloring and list dynamic coloring of planar graphs”, Discrete Appl. Math., 161 (2013), 2207–2212 | DOI | MR | Zbl