Abstract
An r-dynamic k-coloring of a graph G is a proper k-coloring such that any vertex v has 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. Loeb et al. (2018) showed that if G is a planar graph, then χ3 d(G)≤10, and there is a planar graph G with χ3 d(G)=7. Thus, finding an optimal upper bound on χ3 d(G) for a planar graph G is a natural interesting problem. In this paper, we show that χ3 d(G)≤5 if G is a planar triangulation. The upper bound is sharp.
| Original language | English |
|---|---|
| Pages (from-to) | 2988-2994 |
| Number of pages | 7 |
| Journal | Discrete Mathematics |
| Volume | 341 |
| Issue number | 11 |
| DOIs | |
| State | Published - Nov 2018 |
Keywords
- 3-dynamic coloring
- Planar triangulation
Fingerprint
Dive into the research topics of '3-dynamic coloring of planar triangulations'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver