List 3-dynamic coloring of graphs with small maximum average degree - Kim, Seog Jin; Park, Boram (Discrete Mathematics, 2018)
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 χr d(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 chr d(G). Recently, Loeb et al. (0000) showed that the list 3-dynamic chromatic number of a planar graph is at most 10. And Cheng et al. (0000) studied the maximum average condition to have χ3 d(G)≤4,5, or 6. On the other hand, Song et al. (2016) showed that if G is planar with girth at least 6, then χr d(G)≤r+5 for any r≥3. In this paper, we study list 3-dynamic coloring in terms of maximum average degree. We show that ch3 d(G)≤6 if mad(G)<[Formula presented], ch3 d(G)≤7 if mad(G)<[Formula presented], and ch3 d(G)≤8 if mad(G)<3. All of the bounds are tight.
Keywords: Dynamic coloring; List 3-dynamic coloring; Maximum average degree