(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 条
  • [31] Three-coloring planar graphs without short cycles
    Chen, Min
    Raspaud, Andre
    Wang, Weifan
    INFORMATION PROCESSING LETTERS, 2007, 101 (03) : 134 - 138
  • [32] Acyclic Edge Colorings of Planar Graphs Without Short Cycles
    Sun, Xiang-Yong
    Wu, Han-Liang
    OPERATIONS RESEARCH AND ITS APPLICATIONS, PROCEEDINGS, 2008, 8 : 325 - +
  • [33] The 3-colorability of planar graphs without cycles of length 4, 6 and 9
    Kang, Yingli
    Jin, Ligang
    Wang, Yingqian
    DISCRETE MATHEMATICS, 2016, 339 (01) : 299 - 307
  • [34] The Linear Arboricity of Planar Graphs without chordal short cycles
    Wang, Hui-Juan
    Liu, Bin
    Wu, Jian-Liang
    UTILITAS MATHEMATICA, 2012, 87 : 255 - 263
  • [35] Every planar graph without 5-cycles and K4- and adjacent 4-cycles is (2,0,0)-colorable
    Li, Xiangwen
    Yin, Yuxue
    Yu, Gexin
    DISCRETE MATHEMATICS, 2020, 343 (02)
  • [36] Every planar graph without 3-cycles adjacent to 4-cycles and without 6-cycles is (1, 1, 0)-colorable
    Ying Bai
    Xiangwen Li
    Gexin Yu
    Journal of Combinatorial Optimization, 2017, 33 : 1354 - 1364
  • [37] On the 7 Total Colorability of Planar Graphs with Maximum Degree 6 and without 4-cycles
    Lan Shen
    Yingqian Wang
    Graphs and Combinatorics, 2009, 25 : 401 - 407
  • [38] r-Hued coloring of planar graphs without short cycles
    Bu, Yuehua
    Wang, Xiaofang
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2020, 12 (03)
  • [39] On the 7 Total Colorability of Planar Graphs with Maximum Degree 6 and without 4-cycles
    Shen, Lan
    Wang, Yingqian
    GRAPHS AND COMBINATORICS, 2009, 25 (03) : 401 - 407
  • [40] On (3,1)*-choosability of planar graphs without adjacent short cycles
    Chen, Min
    Raspaud, Andre
    DISCRETE APPLIED MATHEMATICS, 2014, 162 : 159 - 166