3-dynamic coloring of planar triangulations |
| |
Authors: | Yoshihiro Asayama Yuki Kawasaki Seog-Jin Kim Atsuhiro Nakamoto Kenta Ozeki |
| |
Institution: | 1. Graduate School of Environment and Information Sciences, Yokohama National University, Japan;2. National Institute of Technology, Hiroshima College, Japan;3. Department of Mathematics Education, Konkuk University, Republic of Korea;4. Faculty of Environment and Information Sciences, Yokohama National University, Japan |
| |
Abstract: | An -dynamic -coloring of a graph is a proper -coloring such that any vertex has at least distinct colors in . The -dynamic chromatic number of a graph is the least such that there exists an -dynamic -coloring of .Loeb et al. (2018) showed that if is a planar graph, then , and there is a planar graph with . Thus, finding an optimal upper bound on for a planar graph is a natural interesting problem. In this paper, we show that if is a planar triangulation. The upper bound is sharp. |
| |
Keywords: | 3-dynamic coloring Planar triangulation |
本文献已被 ScienceDirect 等数据库收录! |
|