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 条
  • [21] Total coloring of planar graphs without adjacent short cycles
    Huijuan Wang
    Bin Liu
    Yan Gu
    Xin Zhang
    Weili Wu
    Hongwei Gao
    Journal of Combinatorial Optimization, 2017, 33 : 265 - 274
  • [22] A Larger Family of Planar Graphs that Satisfy the Total Coloring Conjecture
    Maxfield Leidner
    Graphs and Combinatorics, 2014, 30 : 377 - 388
  • [23] A Larger Family of Planar Graphs that Satisfy the Total Coloring Conjecture
    Leidner, Maxfield
    GRAPHS AND COMBINATORICS, 2014, 30 (02) : 377 - 388
  • [24] Total Coloring of Planar Graphs Without Chordal Short Cycles
    Wang, Huijuan
    Liu, Bin
    Wu, Jianliang
    GRAPHS AND COMBINATORICS, 2015, 31 (05) : 1755 - 1764
  • [25] Total Coloring of Planar Graphs Without Chordal Short Cycles
    Huijuan Wang
    Bin Liu
    Jianliang Wu
    Graphs and Combinatorics, 2015, 31 : 1755 - 1764
  • [26] Total coloring of planar graphs without chordal 7-cycles
    Hua Cai
    Acta Mathematica Sinica, English Series, 2015, 31 : 1951 - 1962
  • [27] Total Coloring of Planar Graphs without Adacent 4-cycles
    Tan, Xiang
    Chen, Hong-Yu
    Wu, Jian-Liang
    OPERATIONS RESEARCH AND ITS APPLICATIONS, PROCEEDINGS, 2009, 10 : 167 - 173
  • [28] Total Coloring of Planar Graphs without Chordal 7-cycles
    Hua CAI
    Acta Mathematica Sinica,English Series, 2015, (12) : 1951 - 1962
  • [29] Total Coloring of Planar Graphs without Chordal 7-cycles
    Cai, Hua
    ACTA MATHEMATICA SINICA-ENGLISH SERIES, 2015, 31 (12) : 1951 - 1962
  • [30] Total Coloring of Planar Graphs Without Some Chordal 6-cycles
    Renyu Xu
    Jianliang Wu
    Huijuan Wang
    Bulletin of the Malaysian Mathematical Sciences Society, 2015, 38 : 561 - 569