Total coloring of planar graphs without adjacent chordal 6-cycles

被引:0
作者
Huijuan Wang
Bin Liu
Xiaoli Wang
Guangmo Tong
Weili Wu
Hongwei Gao
机构
[1] Qingdao University,School of Mathematics and Statistics
[2] Ocean University of China,School of Mathematical Sciences
[3] University of Texas at Dallas,Department of Computer Science
来源
Journal of Combinatorial Optimization | 2017年 / 34卷
关键词
Planar graph; Total coloring; Cycle;
D O I
暂无
中图分类号
学科分类号
摘要
A total coloring of a graph G is a coloring such that no two adjacent or incident elements receive the same color. In this field there is a famous conjecture, named Total Coloring Conjecture, saying that the the total chromatic number of each graph G is at most Δ+2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta +2$$\end{document}. Let G be a planar graph with maximum degree Δ≥7\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta \ge 7$$\end{document} and without adjacent chordal 6-cycles, that is, two cycles of length 6 with chord do not share common edges. In this paper, it is proved that the total chromatic number of G is Δ+1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta +1$$\end{document}, which partly confirmed Total Coloring Conjecture.
引用
收藏
页码:257 / 265
页数:8
相关论文
共 56 条
[1]  
Borodin OV(1989)On the total coloring of planar graphs J Reine Angew Math 394 180-185
[2]  
Borodin OV(1997)Total colorings of planar graphs with large maximum degree J Graph Theory 26 53-59
[3]  
Kostochka AV(2016)Total coloring of planar graphs without short cycles J Comb Optim 31 1650-1664
[4]  
Woodall DR(2011)Local condition for planar graphs of maximum degree 7 to be 8-totally colorable Discret Appl Math 159 760-768
[5]  
Cai H(2009)Planar graphs with maximum degree 8 and without adjacent triangles are Discret Appl Math 157 6035-6043
[6]  
Wu JL(2011)-total-colorable Discret Appl Math 159 157-163
[7]  
Sun L(1996)Total colorings of planar graphs without 6-cycles Discret Math 162 199-214
[8]  
Chang GJ(2008)The total chromatic number of any multigraph with maximum degree five is at most seven SIAM J Discret Math 22 1462-1479
[9]  
Hou JF(2015)Total-coloring of plane graphs with maximum degree nine J Comb Optim 30 675-688
[10]  
Roussel N(2009)Neighbor sum distinguishing total colorings of planar graphs Discret Math 309 6035-6043