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 条
  • [21] Planar graphs with maximum degree 7 and without 5-cycles are 8-totally-colorable
    Shen, Lan
    Wang, Yingqian
    DISCRETE MATHEMATICS, 2010, 310 (17-18) : 2372 - 2379
  • [22] 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
  • [23] Planar graphs without 7-cycles and butterflies are DP-4-colorable
    Kim, Seog-Jin
    Liu, Runrun
    Yu, Gexin
    DISCRETE MATHEMATICS, 2020, 343 (08)
  • [24] A sufficient condition on 3-colorable plane graphs without 5- and 6-circuits
    Bao-gang Xu
    Acta Mathematicae Applicatae Sinica, English Series, 2014, 30 : 765 - 772
  • [25] Every planar graph without 4-cycles and 5-cycles is (3,3)-colorable
    Xiangwen Li
    Jie Liu
    Jian-Bo Lv
    Graphs and Combinatorics, 2023, 39
  • [26] 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
  • [27] 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
  • [28] 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
  • [29] 3-COLORABLE SUBCLASSES OF P8-FREE GRAPHS
    Chudnovsky, Maria
    Stacho, Juraj
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2018, 32 (02) : 1111 - 1138
  • [30] A Sufficient Condition on 3-colorable Plane Graphs Without 5-and 6-circuits
    Xu, Bao-gang
    ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES, 2014, 30 (03): : 765 - 772
12345