On 3-colorable planar graphs without cycles of four lengths

被引：7
作者：
Luo, Xiaofang [1 ]
Chen, Min [1 ]
Wang, Weifan [1 ]
机构：
[1] Zhejiang Normal Univ, Dept Math, Jinhua 321004, Peoples R China
来源：
INFORMATION PROCESSING LETTERS | 2007年 / 103卷 / 04期
基金：
中国国家自然科学基金;
关键词：
planar graph; coloring; cycle; length;
D O I：
10.1016/j.ipl.2007.03.007
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
In this article we prove that planar graphs without 4-, 6-, 7-, and 8-cycles are 3-colorable. (C) 2007 Elsevier B.V. All rights reserved.
引用
收藏
页码：150 / 156
页数：7
相关论文
共 50 条
  • [41] Planar graphs without 4-cycles and close triangles are (2,0,0)-colorable
    Hoskins, Heather
    Liu, Runrun
    Vandenbussche, Jennifer
    Yu, Gexin
    [J]. JOURNAL OF COMBINATORIAL OPTIMIZATION, 2018, 36 (02) : 346 - 364
  • [42] Planar graphs without 4-cycles and intersecting triangles are (1,1,0)-colorable
    Li, Xiangwen
    Liu, Runrun
    Yu, Gexin
    [J]. DISCRETE APPLIED MATHEMATICS, 2021, 304 : 236 - 247
  • [43] Three-coloring planar graphs without short cycles
    Chen, Min
    Raspaud, Andre
    Wang, Weifan
    [J]. INFORMATION PROCESSING LETTERS, 2007, 101 (03) : 134 - 138
  • [44] A note on 3-choosability of planar graphs without certain cycles
    Zhang, L
    Wu, BD
    [J]. DISCRETE MATHEMATICS, 2005, 297 (1-3) : 206 - 209
  • [45] The Alon-Tarsi number of planar graphs without cycles of lengths 4 and l
    Lu, Huajing
    Zhu, Xuding
    [J]. DISCRETE MATHEMATICS, 2020, 343 (05)
  • [46] Planar graphs without 5-cycles or without 6-cycles
    Ma, Qin
    Wu, Jian-Liang
    Yu, Xiao
    [J]. DISCRETE MATHEMATICS, 2009, 309 (10) : 2998 - 3005
  • [47] 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
    [J]. JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 33 (04) : 1354 - 1364
  • [48] The (3,3)-colorability of planar graphs without 4-cycles and 5-cycles
    Liu, Yuhao
    Xiao, Mingyu
    [J]. DISCRETE MATHEMATICS, 2023, 346 (04)
  • [49] Planar graphs without cycles of length 4, 7, 8, or 9 are 3-choosable
    Wang, Yingqian
    Wu, Qian
    Shen, Liang
    [J]. DISCRETE APPLIED MATHEMATICS, 2011, 159 (04) : 232 - 239
  • [50] Vertex arboricity of planar graphs without intersecting 5-cycles
    Cai, Hua
    Wu, Jianliang
    Sun, Lin
    [J]. JOURNAL OF COMBINATORIAL OPTIMIZATION, 2018, 35 (02) : 365 - 372
12345