Total coloring of outer-1-planar graphs with near-independent crossings

被引:0
作者
Xin Zhang
机构
[1] Xidian University,School of Mathematics and Statistics
来源
Journal of Combinatorial Optimization | 2017年 / 34卷
关键词
Outerplanar graph; Outer-1-planar graph; Local structure; Total coloring;
D O I
暂无
中图分类号
学科分类号
摘要
A graph G is outer-1-planar with near-independent crossings if it can be drawn in the plane so that all vertices are on the outer face and |MG(c1)∩MG(c2)|≤1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$|M_G(c_1)\cap M_G(c_2)|\le 1$$\end{document} for any two distinct crossings c1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$c_1$$\end{document} and c2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$c_2$$\end{document} in G, where MG(c)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$M_G(c)$$\end{document} consists of the end-vertices of the two crossed edges that generate c. In Zhang and Liu (Total coloring of pseudo-outerplanar graphs, arXiv:1108.5009), it is showed that the total chromatic number of every outer-1-planar graph with near-independent crossings and with maximum degree at least 5 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}. In this paper we extend the result to maximum degree 4 by proving that the total chromatic number of every outer-1-planar graph with near-independent crossings and with maximum degree 4 is exactly 5.
引用
收藏
页码:661 / 675
页数:14
相关论文
共 47 条
[41]   On total colorings of some special 1-planar graphs [J].
Sun, Lin ;
Wu, Jian-liang ;
Cai, Hua .
ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES, 2017, 33 (03) :607-618
[42]   On Total Colorings of Some Special 1-planar Graphs [J].
Lin SUN ;
Jianliang WU ;
Hua CAI .
Acta Mathematicae Applicatae Sinica, 2017, 33 (03) :607-618
[43]   On total colorings of some special 1-planar graphs [J].
Lin Sun ;
Jian-liang Wu ;
Hua Cai .
Acta Mathematicae Applicatae Sinica, English Series, 2017, 33 :607-618
[44]   Total coloring of 1-toroidal graphs with maximum degree at least 11 and no adjacent triangles [J].
Wang, Tao .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 33 (03) :1090-1105
[45]   Total coloring of 1-toroidal graphs with maximum degree at least 11 and no adjacent triangles [J].
Tao Wang .
Journal of Combinatorial Optimization, 2017, 33 :1090-1105
[46]   (d,1)-total labelling of planar graphs with large girth and high maximum degree [J].
Bazzaro, Fabrice ;
Montassier, Mickael ;
Raspaud, Andre .
DISCRETE MATHEMATICS, 2007, 307 (16) :2141-2151
[47]   (Δ+1)-total choosability of planar graphs with no cycles of length from 4 to k and without close triangles [J].
Chang, Gerard J. ;
Roussel, Nicolas .
DISCRETE MATHEMATICS, 2012, 312 (14) :2126-2130