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 条
  • [41] Adjacent Vertex Distinguishing Edge Coloring of Planar Graphs Without 4-Cycles
    Huang, Danjun
    Zhang, Xiaoxiu
    Wang, Weifan
    Wang, Ping
    BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2020, 43 (04) : 3159 - 3181
  • [42] 2-DISTANCE COLORING OF PLANAR GRAPHS WITHOUT 4-CYCLES AND 5-CYCLES
    Dong, Wei
    Xu, Baogang
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2019, 33 (03) : 1297 - 1312
  • [43] The (3,3)-colorability of planar graphs without 4-cycles and 5-cycles
    Liu, Yuhao
    Xiao, Mingyu
    DISCRETE MATHEMATICS, 2023, 346 (04)
  • [44] Partitioning Planar Graphs without 4-Cycles and 6-Cycles into a Linear Forest and a Forest
    Xiaojie Huang
    Ziwen Huang
    Jian-Bo Lv
    Graphs and Combinatorics, 2023, 39
  • [45] Defective 2-colorings of planar graphs without 4-cycles and 5-cycles
    Sittitrai, Pongpat
    Nakprasit, Kittikorn
    DISCRETE MATHEMATICS, 2018, 341 (08) : 2142 - 2150
  • [46] Partitioning Planar Graphs without 4-Cycles and 6-Cycles into a Linear Forest and a Forest
    Huang, Xiaojie
    Huang, Ziwen
    Lv, Jian-Bo
    GRAPHS AND COMBINATORICS, 2023, 39 (01)
  • [47] The 2-Distance Chromatic Number of Planar Graphs Without 3,4,8-Cycles
    Bu, Yuehua
    Zhang, Zewei
    Zhu, Junlei
    Zhu, Hongguo
    BULLETIN OF THE IRANIAN MATHEMATICAL SOCIETY, 2024, 50 (06)
  • [48] 2-Distance coloring of planar graphs without triangles and intersecting 4-cycles
    Bu, Yuehua
    Zhang, Zewei
    Zhu, Hongguo
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2023, 15 (02)
  • [49] Acyclic 6-choosability of Planar Graphs without 5-cycles and Adjacent 4-cycles
    Sun, Lin
    ACTA MATHEMATICA SINICA-ENGLISH SERIES, 2021, 37 (06) : 992 - 1004
  • [50] Partitioning planar graphs without 4-cycles and 5-cycles into two forests with a specific condition
    Tangjai, Wipawee
    Nakprasit, Kittikorn
    Nakprasit, Keaitsuda Maneeruk
    Sittitrai, Pongpat
    DISCRETE APPLIED MATHEMATICS, 2024, 342 : 347 - 354
12345