An improved upper bound for the dynamic list coloring of 1-planar graphs

Abstract

A graph is 1-planar if it can be drawn in the plane such that each of its edges is crossed at most once. A dynamic coloring of a graph G is a proper vertex coloring such that for each vertex of degree at least 2, its neighbors receive at least two different colors. The list dynamic chromatic number chd(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. In this paper, we show that if G is a 1-planar graph, then chd(G)≤10. This improves a result by Zhang and Li [16], which says that every 1-planar graph G has chd(G)≤11.

Keywords

• 1-planar graph
• dynamic coloring
• list coloring