(1,0,0)-Colorability of planar graphs without prescribed short cycles

被引:0
|
作者
Bu, Yuehua [1 ]
Xu, Jinghan [1 ]
Wang, Yingqian [1 ]
机构
[1] Zhejiang Normal Univ, Coll Math Phys & Informat Engn, Jinhua 321004, Peoples R China
关键词
Planar graph; Steinberg conjecture; Improper coloring; Cycle; LENGTH; 4;
D O I
10.1007/s10878-013-9653-5
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
Let be non-negative integers. A graph is -colorable, if the vertex set of can be partitioned into subsets such that the subgraph induced by has maximum degree at most for . Let be the family of planar graphs with cycles of length neither 4 nor 8. In this paper, we prove that a planar graph in is -colorable if it has no cycle of length for some . Together with other known related results, this completes a neat conclusion on the -colorability of planar graphs without prescribed short cycles, more precisely, for every triple , planar graphs without cycles of length 4, or are -colorable whenever 4 < i < j <= 9.
引用
收藏
页码:627 / 646
页数:20
相关论文
共 50 条
  • [41] Acyclic edge colouring of planar graphs without short cycles
    Borowiecki, Mieczyslaw
    Fiedorowicz, Anna
    DISCRETE MATHEMATICS, 2010, 310 (09) : 1445 - 1455
  • [42] On 3-colorable planar graphs without short cycles
    Chen, Min
    Wang, Weifan
    APPLIED MATHEMATICS LETTERS, 2008, 21 (09) : 961 - 965
  • [43] DP-coloring on planar graphs without given adjacent short cycles
    Huang, Danjun
    Qi, Jingran
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2021, 13 (02)
  • [44] A note on list edge coloring of planar graphs without adjacent short cycles
    Hu, Linna
    Song, Huimin
    Wu, Jian-Liang
    ARS COMBINATORIA, 2019, 143 : 3 - 12
  • [45] THE LINEAR 2-ARBORICITY OF PLANAR GRAPHS WITHOUT ADJACENT SHORT CYCLES
    Chen, Hong-Yu
    Tan, Xiang
    Wu, Jian-Liang
    BULLETIN OF THE KOREAN MATHEMATICAL SOCIETY, 2012, 49 (01) : 145 - 154
  • [46] The linear arboricity of planar graphs with no short cycles
    Wu, Jian-Liang
    Hou, Jian-Feng
    Liu, Gui-Zhen
    THEORETICAL COMPUTER SCIENCE, 2007, 381 (1-3) : 230 - 233
  • [47] Planar graphs without 5-cycles or without 6-cycles
    Ma, Qin
    Wu, Jian-Liang
    Yu, Xiao
    DISCRETE MATHEMATICS, 2009, 309 (10) : 2998 - 3005
  • [48] List injective coloring of a class of planar graphs without short cycles
    Bu, Yuehua
    Huang, Chaoyuan
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2018, 10 (05)
  • [49] Planar graphs without short even cycles are near-bipartite
    Liu, Runrun
    Yu, Gexin
    DISCRETE APPLIED MATHEMATICS, 2020, 284 : 626 - 630
  • [50] On acyclic 4-choosability of planar graphs without short cycles
    Chen, Min
    Raspaud, Andre
    DISCRETE MATHEMATICS, 2010, 310 (15-16) : 2113 - 2118