Skip to main navigation Skip to search Skip to main content

3-dynamic coloring of planar triangulations

  • Yoshihiro Asayama
  • , Yuki Kawasaki
  • , Seog Jin Kim
  • , Atsuhiro Nakamoto
  • , Kenta Ozeki
  • Yokohama National University
  • National Institute of Technology, Hiroshima College

Research output: Contribution to journal › Article › peer-review

10 Scopus citations

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 languageEnglish
Pages (from-to)2988-2994
Number of pages7
JournalDiscrete Mathematics
Volume341
Issue number11
DOIs
StatePublished - 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