Dynamic coloring of graphs having no K5 minor

被引：8
|
作者：
Kim, Younjin [1 ]
Lee, Sang June [2 ]
Oum, Sang-il [3 ,4 ]
机构：
[1] Ewha Womans Univ, Dept Math, Seoul, South Korea
[2] Duksung Womens Univ, Dept Math, Seoul, South Korea
[3] Korea Adv Inst Sci & Technol, Dept Math Sci, Daejeon, South Korea
[4] KIAS, Sch Math, Seoul, South Korea
来源：
DISCRETE APPLIED MATHEMATICS | 2016年 / 206卷
基金：
新加坡国家研究基金会;
关键词：
Dynamic coloring; Minor-free graph; Four color theorem; Hadwiger's conjecture; LOCAL CHROMATIC NUMBER; CONJECTURE;
D O I：
10.1016/j.dam.2016.01.022
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
We prove that every simple connected graph with no K5 minor admits a proper 4-coloring such that the neighborhood of each vertex v having more than one neighbor is not monochromatic, unless the graph is isomorphic to the cycle of length 5. This generalizes the result on planar graphs by 5.-J. Kim, W.J. Park and the second author [Discrete Appl. Math. 161 (2013) 2207-22121. (C) 2016 Elsevier B.V. All rights reserved.
引用
收藏
页码：81 / 89
页数：9
相关论文
共 28 条
  • [11] Element deletion changes in dynamic coloring of graphs
    Miao, Lian-Ying
    Lai, Hong-Jian
    Guo, Yan-Fang
    Miao, Zhengke
    DISCRETE MATHEMATICS, 2016, 339 (05) : 1600 - 1604
  • [12] Dynamic list coloring of 1-planar graphs
    Zhang, Xin
    Li, Yan
    DISCRETE MATHEMATICS, 2021, 344 (05)
  • [13] The dynamic coloring numbers of Pseudo-Halin graphs
    Meng, XY
    Miao, LY
    Su, BT
    Li, RS
    ARS COMBINATORIA, 2006, 79 : 3 - 9
  • [14] List Dynamic 4-Coloring of Planar Graphs
    Kim, Seog-Jin
    Lee, Sang June
    Lian, Xiaopan
    Zhu, Xuding
    GRAPHS AND COMBINATORICS, 2025, 41 (01)
  • [15] Optimal r-dynamic coloring of sparse graphs
    Dan Yi
    Junlei Zhu
    Lixia Feng
    Jiaxin Wang
    Mengyini Yang
    Journal of Combinatorial Optimization, 2019, 38 : 545 - 555
  • [16] Graphs with no K9=minor are 10-colorable
    Rolek, Martin
    JOURNAL OF GRAPH THEORY, 2020, 93 (04) : 560 - 565
  • [17] Clustered coloring of (path+2K1)-free graphs on surfaces
    Dvorak, Zdenek
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2025, 173 : 45 - 67
  • [18] An improved upper bound for the dynamic list coloring of 1-planar graphs
    Hu, Xiaoxue
    Kong, Jiangxu
    AIMS MATHEMATICS, 2022, 7 (05): : 7337 - 7348
  • [19] List 3-dynamic coloring of graphs with small maximum average degree
    Kim, Seog-Jin
    Park, Boram
    DISCRETE MATHEMATICS, 2018, 341 (05) : 1406 - 1418
  • [20] The structure and the list 3-dynamic coloring of outer-1-planar graphs
    Li, Yan
    Zhang, Xin
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2021, 23 (03)
123