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 C_{5}. (Note that χ_{d}(C_{5})=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_{5}. We also study the corresponding list coloring called a *list dynamic coloring*.

This is joint work with Seog-Jin Kim and Won-Jin Park.

Tags: 이상준