KAIST Discrete Math Seminar

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 C₅. (Note that χ_d(C₅)=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 C₅. We also study the corresponding list coloring called a list dynamic coloring.
This is joint work with Seog-Jin Kim and Won-Jin Park.