(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 条
  • [21] Total coloring of planar graphs without short cycles
    Cai, Hua
    Wu, Jianliang
    Sun, Lin
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2016, 31 (04) : 1650 - 1664
  • [22] Equitable colorings of planar graphs without short cycles
    Nakprasit, Keaitsuda
    Nakprasit, Kittikorn
    THEORETICAL COMPUTER SCIENCE, 2012, 465 : 21 - 27
  • [23] Edge choosability of planar graphs without short cycles
    Wang, WF
    SCIENCE IN CHINA SERIES A-MATHEMATICS, 2005, 48 (11): : 1531 - 1544
  • [24] Total coloring of planar graphs without short cycles
    Hua Cai
    Jianliang Wu
    Lin Sun
    Journal of Combinatorial Optimization, 2016, 31 : 1650 - 1664
  • [25] Every planar graph without 3-cycles adjacent to 4-cycles and without 6-cycles is (1,1,0)-colorable
    Bai, Ying
    Li, Xiangwen
    Yu, Gexin
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 33 (04) : 1354 - 1364
  • [26] Acyclic 4-colorability of planar graphs without cycles of length 4 or 6
    Borodin O.V.
    Journal of Applied and Industrial Mathematics, 2010, 4 (04) : 490 - 495
  • [27] Total coloring of planar graphs without adjacent short cycles
    Wang, Huijuan
    Liu, Bin
    Gu, Yan
    Zhang, Xin
    Wu, Weili
    Gao, Hongwei
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 33 (01) : 265 - 274
  • [28] Total coloring of planar graphs without adjacent short cycles
    Huijuan Wang
    Bin Liu
    Yan Gu
    Xin Zhang
    Weili Wu
    Hongwei Gao
    Journal of Combinatorial Optimization, 2017, 33 : 265 - 274
  • [29] Total Coloring of Planar Graphs Without Chordal Short Cycles
    Wang, Huijuan
    Liu, Bin
    Wu, Jianliang
    GRAPHS AND COMBINATORICS, 2015, 31 (05) : 1755 - 1764
  • [30] Total Coloring of Planar Graphs Without Chordal Short Cycles
    Huijuan Wang
    Bin Liu
    Jianliang Wu
    Graphs and Combinatorics, 2015, 31 : 1755 - 1764