On total chromatic number of planar graphs without 4-cycles

被引:0
|
作者
Ying-qian Wang
Min-le Shangguan
Qiao Li
机构
[1] Zhejiang Normal University,College of Mathematics, Physics and Information Engineering
[2] Shanghai Jiaotong University,Department of Applied Mathematics
来源
Science in China Series A: Mathematics | 2007年 / 50卷
关键词
total chromatic number; planar graph; -subgraph; 05C40;
D O I
暂无
中图分类号
学科分类号
摘要
Let G be a simple graph with maximum degree Δ(G) and total chromatic number xve(G). Vizing conjectured that Δ(G) + 1 ⩽ Xve(G) ⩽ δ(G) + 2 (Total Chromatic Conjecture). Even for planar graphs, this conjecture has not been settled yet. The unsettled difficult case for planar graphs is Δ(G) = 6. This paper shows that if G is a simple planar graph with maximum degree 6 and without 4-cycles, then xve(G) ⩽ 8. Together with the previous results on this topic, this shows that every simple planar graph without 4-cycles satisfies the Total Chromatic Conjecture.
引用
收藏
页码:81 / 86
页数:5
相关论文
共 50 条
  • [31] Equitable and list equitable colorings of planar graphs without 4-cycles
    Dong, Aijun
    Li, Guojun
    Wang, Guanghui
    DISCRETE MATHEMATICS, 2013, 313 (15) : 1610 - 1619
  • [32] The 2-surviving rate of planar graphs without 4-cycles
    Wang, Weifan
    Kong, Jiangxu
    Zhang, Lianzhu
    THEORETICAL COMPUTER SCIENCE, 2012, 457 : 158 - 165
  • [33] ACYCLIC 5-CHOOSABILITY OF PLANAR GRAPHS WITHOUT 4-CYCLES
    Borodin, O. V.
    Ivanova, A. O.
    SIBERIAN MATHEMATICAL JOURNAL, 2011, 52 (03) : 411 - 425
  • [34] Acyclic 5-choosability of planar graphs without 4-cycles
    Borodin O.V.
    Ivanova A.O.
    Siberian Mathematical Journal, 2011, 52 (3) : 411 - 425
  • [35] Planar graphs without 4-cycles adjacent to triangles are 4-choosable
    Cheng, Panpan
    Chen, Min
    Wang, Yingqian
    DISCRETE MATHEMATICS, 2016, 339 (12) : 3052 - 3057
  • [36] Equitable coloring of planar graphs without 5-cycles and chordal 4-cycles
    Wu, Xianxi
    Huang, Danjun
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2024, 16 (08)
  • [37] Edge DP-coloring of planar graphs without 4-cycles and specific cycles
    Jumnongnit, Patcharapan
    Nakprasit, Kittikorn
    Ruksasakchai, Watcharintorn
    Sittitrai, Pongpat
    DISCRETE MATHEMATICS, 2025, 348 (04)
  • [38] Adjacent Vertex Distinguishing Edge Coloring of Planar Graphs Without 4-Cycles
    Danjun Huang
    Xiaoxiu Zhang
    Weifan Wang
    Ping Wang
    Bulletin of the Malaysian Mathematical Sciences Society, 2020, 43 : 3159 - 3181
  • [39] List-Coloring the Squares of Planar Graphs without 4-Cycles and 5-Cycles
    Cranston, Daniel W.
    Jaeger, Bobby
    JOURNAL OF GRAPH THEORY, 2017, 85 (04) : 721 - 737
  • [40] A note on edge-choosability of planar graphs without intersecting 4-cycles
    Ma Q.
    Wang J.
    Cai J.
    Zhang S.
    Journal of Applied Mathematics and Computing, 2011, 36 (1-2) : 367 - 372