On 3-colorability of planar graphs without adjacent short cycles

被引：0
作者：
YingQian Wang
XiangHua Mao
HuaJing Lu
WeiFan Wang
机构：
[1] Zhejiang Normal University,College of Mathematics, Physics and Information Engineering
[2] Ningbo Dahongying University,College of Basic Science
来源：
Science China Mathematics | 2010年 / 53卷
关键词：
planar graph; coloring; extension; cycle; 05C15; 68R10;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
A short cycle means a cycle of length at most 7. In this paper, we prove that planar graphs without adjacent short cycles are 3-colorable. This improves a result of Borodin et al. (2005).
引用
收藏
页码：1129 / 1132
页数：3
相关论文
共 50 条
  • [31] A Note on List Edge and List Total Coloring of Planar Graphs without Adjacent Short Cycles
    Wang, Hui Juan
    Wu, Jian Liang
    ACTA MATHEMATICA SINICA-ENGLISH SERIES, 2014, 30 (01) : 91 - 96
  • [32] Adjacent vertex distinguishing edge coloring of planar graphs without 3-cycles
    Huang, Danjun
    Zhang, Xiaoxiu
    Wang, Weifan
    Finbow, Stephen
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2020, 12 (04)
  • [33] Total coloring of planar graphs without short cycles
    Cai, Hua
    Wu, Jianliang
    Sun, Lin
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2016, 31 (04) : 1650 - 1664
  • [34] Equitable colorings of planar graphs without short cycles
    Nakprasit, Keaitsuda
    Nakprasit, Kittikorn
    THEORETICAL COMPUTER SCIENCE, 2012, 465 : 21 - 27
  • [35] Total coloring of planar graphs without short cycles
    Hua Cai
    Jianliang Wu
    Lin Sun
    Journal of Combinatorial Optimization, 2016, 31 : 1650 - 1664
  • [36] Edge coloring of planar graphs without adjacent 7-cycles
    Zhang, Wenwen
    Wu, Jian-Liang
    THEORETICAL COMPUTER SCIENCE, 2018, 739 : 59 - 64
  • [37] The linear arboricity of planar graphs without adjacent 4-cycles
    Wang, Huijuan
    Liu, Bin
    Wu, Jianliang
    UTILITAS MATHEMATICA, 2013, 91 : 143 - 153
  • [38] Total colorings of planar graphs without adjacent 5-cycles
    Chang, Jian
    Wang, Hui-Juan
    ARS COMBINATORIA, 2019, 142 : 329 - 344
  • [39] On 3-colorable planar graphs without prescribed cycles
    Wang, Weifan
    Chen, Min
    DISCRETE MATHEMATICS, 2007, 307 (22) : 2820 - 2825
  • [40] 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
12345