Department of Mathematics and Computer Science, Emory University, Atlanta, Georgia, USA
A dynamic coloring of a graph G is a proper coloring of the vertex set V(G) such that for each vertex of degree at least 2, its neighbors receive at least two distinct colors. A dynamic k-coloring of a graph is a dynamic coloring with k colors. Note that the gap χd(G) – χ(G) could be arbitrarily large for some graphs. An interesting problem is to study which graphs have small values of χd(G) – χ(G).
One of the most interesting problems about dynamic chromatic numbers is to find upper bounds of χd(G)$ for planar graphs G. Lin and Zhao (2010) and Fan, Lai, and Chen (recently) showed that for every planar graph G, we have χd(G)≤5, and it was conjectured that χd(G)≤4 if G is a planar graph other than C5. (Note that χd(C5)=5.)
As a partial answer, Meng, Miao, Su, and Li (2006) showed that the dynamic chromatic number of Pseudo-Halin graphs, which are planar graphs, are at most 4, and Kim and Park (2011) showed that χd(G)≤4 if G is a planar graph with girth at least 7.
In this talk we settle the above conjecture that χd≤4 if G is a planar graph other than C5. We also study the corresponding list coloring called a list dynamic coloring.
This is joint work with Seog-Jin Kim and Won-Jin Park.