A sufficient condition for planar graphs with girth 5 to be (1,6)-colorable

被引：1
作者：
Zhang, Ganchao [1 ]
Chen, Min [1 ]
Wang, Weifan [1 ]
机构：
[1] Zhejiang Normal Univ, Sch Math Sci, Jinhua 321004, Peoples R China
来源：
APPLIED MATHEMATICS AND COMPUTATION | 2024年 / 474卷
关键词：
Improper coloring; Planar graphs; Cycle; Discharging method; LENGTH; 4; CYCLES; COLORINGS; MAP;
D O I：
10.1016/j.amc.2024.128706
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
A graph G is (d(1), d(2))-colorable if its vertices can be partitioned into two subsets V-1 and V-2 such that Delta(G[V-1]) <= d(1) and Delta(G[V-2]) <= d(2) . Let G(5) denote the family of planar graphs with girth at least 5. In this paper, we prove that every graph in G(5) without adjacent 5-cycles is (1, 6)-colorable.
引用
收藏
页数：8
相关论文
共 21 条
  • [1] EVERY PLANAR MAP IS 4 COLORABLE .1. DISCHARGING
    APPEL, K
    HAKEN, W
    [J]. ILLINOIS JOURNAL OF MATHEMATICS, 1977, 21 (03) : 429 - 490
  • [2] EVERY PLANAR MAP IS 4 COLORABLE .2. REDUCIBILITY
    APPEL, K
    HAKEN, W
    KOCH, J
    [J]. ILLINOIS JOURNAL OF MATHEMATICS, 1977, 21 (03) : 491 - 567
  • [3] Defective 2-colorings of sparse graphs
    Borodin, O. V.
    Kostochka, A. V.
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2014, 104 : 72 - 80
  • [4] Vertex Decompositions of Sparse Graphs into an Edgeless Subgraph and a Subgraph of Maximum Degree at Most k
    Borodin, O. V.
    Ivanova, A. O.
    Montassier, M.
    Ochem, P.
    Raspaud, A.
    [J]. JOURNAL OF GRAPH THEORY, 2010, 65 (02) : 83 - 93
  • [5] Planar graphs without cycles of length 4 or 5 are (2,0,0)-colorable
    Chen, Ming
    Wang, Yingqian
    Liu, Peipei
    Xu, Jinghan
    [J]. DISCRETE MATHEMATICS, 2016, 339 (02) : 886 - 905
  • [6] (1, k)-Coloring of Graphs with Girth at Least Five on a Surface
    Choi, Hojin
    Choi, Ilkyoo
    Jeong, Jisu
    Suh, Geewon
    [J]. JOURNAL OF GRAPH THEORY, 2017, 84 (04) : 521 - 535
  • [7] Planar graphs with girth at least 5 are (3,4)-colorable
    Choi, Ilkyoo
    Yu, Gexin
    Zhang, Xia
    [J]. DISCRETE MATHEMATICS, 2019, 342 (12)
  • [8] Planar graphs with girth at least 5 are (3,5)-colorable
    Choi, Ilkyoo
    Raspaud, Andre
    [J]. DISCRETE MATHEMATICS, 2015, 338 (04) : 661 - 667
  • [9] DEFECTIVE COLORINGS OF GRAPHS IN SURFACES - PARTITIONS INTO SUBGRAPHS OF BOUNDED VALENCY
    COWEN, LJ
    COWEN, RH
    WOODALL, DR
    [J]. JOURNAL OF GRAPH THEORY, 1986, 10 (02) : 187 - 195
  • [10] Eaton N., 1999, B I COMBINAT APPL, V25, P79
123