On list 3-dynamic coloring of near-triangulations

Abstract

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,de{g}_G(v)\}$ distinct colors in $N_G(v)$. The $r$-dynamic chromatic number ${\chi }_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 $c{h}_r^d(G)$. Loeb et al. $[11]$ showed that $c{h}_3^d(G)\le 10$ for every planar graph $G$, and there is a planar graph $G$ with ${\chi }_3^d(G)=7$. In this paper, we study a special class of planar graphs which have better upper bounds of $c{h}_3^d(G)$. We prove that $c{h}_3^d(G)\le 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.