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 条
[31]   Total Coloring of Planar Graphs Without Some Chordal 6-cycles [J].
Renyu Xu ;
Jianliang Wu ;
Huijuan Wang .
Bulletin of the Malaysian Mathematical Sciences Society, 2015, 38 :561-569
[32]   Total coloring of planar graphs without adjacent chordal 6-cycles [J].
Wang, Huijuan ;
Liu, Bin ;
Wang, Xiaoli ;
Tong, Guangmo ;
Wu, Weili ;
Gao, Hongwei .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 34 (01) :257-265
[33]   A note on the total coloring of planar graphs without adjacent 4-cycles [J].
Wang, Hui-Juan ;
Wu, Jian-Liang .
DISCRETE MATHEMATICS, 2012, 312 (11) :1923-1926
[34]   Total coloring of planar graphs without adjacent chordal 6-cycles [J].
Huijuan Wang ;
Bin Liu ;
Xiaoli Wang ;
Guangmo Tong ;
Weili Wu ;
Hongwei Gao .
Journal of Combinatorial Optimization, 2017, 34 :257-265
[35]   Total coloring of planar graphs without adjacent chordal 5-cycles [J].
Tian, Jingjing ;
Wang, Huijuan ;
Wu, Jianliang .
UTILITAS MATHEMATICA, 2013, 91 :13-23
[36]   Total coloring of planar graphs with 7-cycles containing at most two chords [J].
Xu, Renyu ;
Wu, Jian-Liang .
THEORETICAL COMPUTER SCIENCE, 2014, 520 :124-129
[37]   On total colorings of 1-planar graphs [J].
Zhang, Xin ;
Hou, Jianfeng ;
Liu, Guizhen .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2015, 30 (01) :160-173
[38]   On total colorings of 1-planar graphs [J].
Xin Zhang ;
Jianfeng Hou ;
Guizhen Liu .
Journal of Combinatorial Optimization, 2015, 30 :160-173
[39]   A note on total colorings of 1-planar graphs [J].
Czap, Julius .
INFORMATION PROCESSING LETTERS, 2013, 113 (14-16) :516-517
[40]   ON (p, 1)-TOTAL LABELLING OF SOME 1-PLANAR GRAPHS [J].
Niu, Bei ;
Zhang, Xin .
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2021, 41 (02) :531-558