(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
来源：
JOURNAL OF COMBINATORIAL OPTIMIZATION | 2015年 / 30卷 / 03期
关键词：
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 条
  • [1] (1,0,0)-colorability of planar graphs without cycles of length 4, 5 or 9
    Wang, Yingqian
    Yang, Yaochou
    DISCRETE MATHEMATICS, 2014, 326 : 44 - 49
  • [2] Improper colorability of planar graphs without prescribed short cycles
    Wang, Yingqian
    Xu, Jinghan
    DISCRETE MATHEMATICS, 2014, 322 : 5 - 14
  • [3] (1,0,0)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(1,0,0)$$\end{document}-Colorability of planar graphs without prescribed short cycles
    Yuehua Bu
    Jinghan Xu
    Yingqian Wang
    Journal of Combinatorial Optimization, 2015, 30 (3) : 627 - 646
  • [4] On 3-colorability of planar graphs without adjacent short cycles
    Wang YingQian
    Mao XiangHua
    Lu, HuaJing
    Wang WeiFan
    SCIENCE CHINA-MATHEMATICS, 2010, 53 (04) : 1129 - 1132
  • [5] On 3-colorability of planar graphs without adjacent short cycles
    WANG YingQian 1
    2 College of Basic Science
    Science China(Mathematics), 2010, 53 (04) : 1129 - 1132
  • [6] On 3-colorability of planar graphs without adjacent short cycles
    YingQian Wang
    XiangHua Mao
    HuaJing Lu
    WeiFan Wang
    Science China Mathematics, 2010, 53 : 1129 - 1132
  • [7] Planar graphs without cycles of length 4 or 5 are (3,0,0)-colorable
    Hill, Owen
    Smith, Diana
    Wang, Yingqian
    Xu, Lingji
    Yu, Gexin
    DISCRETE MATHEMATICS, 2013, 313 (20) : 2312 - 2317
  • [8] Planar Graphs Without Adjacent Cycles of Length at Most Five are (2, 0, 0)-Colorable
    Xiangwen Li
    Qin Shen
    Fanyu Tian
    Bulletin of the Malaysian Mathematical Sciences Society, 2021, 44 : 1167 - 1194
  • [9] The (3,3)-colorability of planar graphs without 4-cycles and 5-cycles
    Liu, Yuhao
    Xiao, Mingyu
    DISCRETE MATHEMATICS, 2023, 346 (04)
  • [10] Planar Graphs Without Adjacent Cycles of Length at Most Five are (2,0,0)-Colorable
    Li, Xiangwen
    Shen, Qin
    Tian, Fanyu
    BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2021, 44 (03) : 1167 - 1194
12345