2019/09/10 by Ruijuan Gu, Seog-Jin Kim, Gu, Ruijuan +5
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1909.04533
arxiv created 2019/09/10 · arxiv updated 2019/09/11
An r-dynamic k-coloring of a graph G is a proper k-coloring such that for any vertex v, there are at least min\r, degG(v) \ distinct colors in NG(v). The r-dynamic chromatic number χrd(G) of a graph G is the least k such that there exists an r-dynamic k-coloring of G. The list r-dynamic chromatic number of a graph G is denoted by chrd(G). Loeb et al. [11] showed that ch3d(G)≤ 10 for every planar graph G, and there is a planar graph G with χ3d(G)= 7. In this paper, we study a special class of planar graphs which have better upper bounds of ch3d(G). We prove that ch3d(G) ≤ 6 if G is a planar graph which is near-triangulation, where a near-triangulation is a planar graph whose bounded faces are all 3-cycles.