Dynamic coloring and list dynamic coloring of planar graphs

Abstract

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. The dynamic chromatic number chi(d)(G) of a graph G is the least number k such that G has a dynamic coloring with k colors. We show that chi(d)(G) <= 4 for every planar graph except C-5, which was conjectured in Chen et al. (2012)[5]. The list dynamic chromatic number ch(d)(G) of G is the least number k such that for any assignment of k-element lists to the vertices of G, there is a dynamic coloring of G where the color on each vertex is chosen from its list. Based on Thomassen's (1994) result [141 that every planar graph is 5-choosable, an interesting question is whether the list dynamic chromatic number of every planar graph is at most 5 or not. We answer this question by showing that chd(G) <= 5 for every planar graph. (C) 2013 Elsevier B.V. All rights reserved.