Total coloring of 1-toroidal graphs with maximum degree at least 11 and no adjacent triangles

被引:0
作者
Tao Wang
机构
[1] Henan University,Institute of Applied Mathematics
来源
Journal of Combinatorial Optimization | 2017年 / 33卷
关键词
Total coloring; 1-Toroidal graph; 1-Planar graph; Total coloring conjecture;
D O I
暂无
中图分类号
学科分类号
摘要
A total coloring of a graph G is an assignment of colors to the vertices and the edges of G such that every pair of adjacent/incident elements receive distinct colors. The total chromatic number of a graph G, denoted by χ′′(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\chi ''(G)$$\end{document}, is the minimum number of colors in a total coloring of G. The well-known total coloring conjecture (TCC) says that every graph with maximum degree Δ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta $$\end{document} admits a total coloring with 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} colors. A graph is 1-toroidal if it can be drawn in torus such that every edge crosses at most one other edge. In this paper, we investigate the total coloring of 1-toroidal graphs, and prove that the TCC holds for the 1-toroidal graphs with maximum degree at least 11 and some restrictions on the triangles. Consequently, if G is a 1-toroidal graph with maximum degree Δ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta $$\end{document} at least 11 and without adjacent triangles, then G admits a total coloring with 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} colors.
引用
收藏
页码:1090 / 1105
页数:15
相关论文
共 25 条
[1]  
Borodin OV(1989)On the total coloring of planar graphs J Reine Angew Math 394 180-185
[2]  
Borodin OV(1995)A new proof of the J Graph Theory 19 507-521
[3]  
Borodin OV(2001) color theorem Discrete Appl Math 114 29-41
[4]  
Kostochka AV(1977)Acyclic colouring of 1-planar graphs Discrete Math 17 161-163
[5]  
Raspaud A(1996)The total coloring of a multigraph with maximal degree Discrete Math 162 199-214
[6]  
Sopena E(1965)The total chromatic number of any multigraph with maximum degree five is at most seven Abh Math Sem Univ Hambg 29 107-117
[7]  
Kostochka AV(1971)Ein sechsfarbenproblem auf der Kugel Israel J Math 9 396-402
[8]  
Kostochka AV(1999)On the total coloring of certain graphs J Graph Theory 31 67-73
[9]  
Ringel G(1971)On total 9-coloring planar graphs of maximum degree seven J London Math Soc 2 405-408
[10]  
Rosenfeld M(1965)On total chromatic number of a graph Diskret Anal 5 9-17