3-dynamic coloring of planar triangulations

被引:4
作者
Asayama, Yoshihiro [1 ]
Kawasaki, Yuki [2 ]
Kim, Seog-Jin [3 ]
Nakamoto, Atsuhiro [4 ]
Ozeki, Kenta [4 ]
机构
[1] Yokohama Natl Univ, Grad Sch Environm & Informat Sci, Yokohama, Kanagawa, Japan
[2] Hiroshima Coll, Natl Inst Technol, Hiroshima, Japan
[3] Konkuk Univ, Dept Math Educ, Seoul, South Korea
[4] Yokohama Natl Univ, Fac Environm & Informat Sci, Yokohama, Kanagawa, Japan
基金
新加坡国家研究基金会;
关键词
3-dynamic coloring; Planar triangulation; MAXIMUM AVERAGE DEGREE; GRAPHS; SQUARE;
D O I
10.1016/j.disc.2018.07.020
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
An r-dynamic k-coloring of a graph G is a proper k-coloring such that any vertex v has at least min{r, deg(G)(v)} distinct colors in N-G(v). The r-dynamic chromatic number chi(d)(r)(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 chi(d)(3)(G) <= 10, and there is a planar graph G with chi(d)(3)(G) = 7. Thus, finding an optimal upper bound on chi(d)(3)(G) for a planar graph G is a natural interesting problem. In this paper, we show that chi(d)(3)(G) <= 5 if G is a planar triangulation. The upper bound is sharp. (C) 2018 Elsevier B.V. All rights reserved.
引用
收藏
页码:2988 / 2994
页数:7
相关论文
共 17 条
  • [1] A counterexample to Montgomery's conjecture on dynamic colourings of regular graphs
    Bowler, N.
    Erde, J.
    Lehner, F.
    Merker, M.
    Pitz, M.
    Stavropoulos, K.
    [J]. DISCRETE APPLIED MATHEMATICS, 2017, 229 : 151 - 153
  • [2] r-hued coloring of sparse graphs
    Cheng, Jian
    Lai, Hong-Jian
    Lorenzen, Kate J.
    Luo, Rong
    Thompson, Joshua C.
    Zhang, Cun-Quan
    [J]. DISCRETE APPLIED MATHEMATICS, 2018, 237 : 75 - 81
  • [3] Coloring squares of planar graphs with girth six
    Dvorak, Zdenek
    Kral, Daniel
    Nejedly, Pavel
    Skrekovski, Riste
    [J]. EUROPEAN JOURNAL OF COMBINATORICS, 2008, 29 (04) : 838 - 849
  • [4] On r-dynamic coloring of graphs
    Jahanbekam, Sogol
    Kim, Jaehoon
    Suil, O.
    West, Douglas B.
    [J]. DISCRETE APPLIED MATHEMATICS, 2016, 206 : 65 - 72
  • [5] On r-dynamic coloring of grids
    Kang, Ross
    Muller, Tobias
    West, Douglas B.
    [J]. DISCRETE APPLIED MATHEMATICS, 2015, 186 : 286 - 290
  • [6] List 3-dynamic coloring of graphs with small maximum average degree
    Kim, Seog-Jin
    Park, Boram
    [J]. DISCRETE MATHEMATICS, 2018, 341 (05) : 1406 - 1418
  • [7] Coloring the square of graphs whose maximum average degree is less than 4
    Kim, Seog-Jin
    Park, Boram
    [J]. DISCRETE MATHEMATICS, 2016, 339 (04) : 1251 - 1260
  • [8] Dynamic coloring and list dynamic coloring of planar graphs
    Kim, Seog-Jin
    Lee, Sang June
    Park, Won-Jin
    [J]. DISCRETE APPLIED MATHEMATICS, 2013, 161 (13-14) : 2207 - 2212
  • [9] 3-dynamic coloring and list 3-dynamic coloring of K1,3-free graphs
    Li, Hao
    Lai, Hong-Jian
    [J]. DISCRETE APPLIED MATHEMATICS, 2017, 222 : 166 - 171
  • [10] Dynamic coloring parameters for graphs with given genus
    Loeb, Sarah
    Mahoney, Thomas
    Reiniger, Benjamin
    Wise, Jennifer
    [J]. DISCRETE APPLIED MATHEMATICS, 2018, 235 : 129 - 141