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 条
  • [1] Total coloring of outer-1-planar graphs with near-independent crossings
    Zhang, Xin
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 34 (03) : 661 - 675
  • [2] List Edge Coloring of Outer-1-planar Graphs
    Zhang, Xin
    ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES, 2020, 36 (03): : 737 - 752
  • [3] List Edge Coloring of Outer-1-planar Graphs
    Xin ZHANG
    Acta Mathematicae Applicatae Sinica, 2020, 36 (03) : 737 - 752
  • [4] List Edge Coloring of Outer-1-planar Graphs
    Xin Zhang
    Acta Mathematicae Applicatae Sinica, English Series, 2020, 36 : 737 - 752
  • [5] The structure and the list 3-dynamic coloring of outer-1-planar graphs
    Li, Yan
    Zhang, Xin
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2021, 23 (03)
  • [6] Light paths and edges in families of outer-1-planar graphs
    Zhang, Xin
    Lan, Jingfen
    Li, Bi
    Zhu, Qiang
    INFORMATION PROCESSING LETTERS, 2018, 136 : 83 - 89
  • [7] Total Coloring of Dumbbell Maximal Planar Graphs
    Zhou, Yangyang
    Zhao, Dongyang
    Ma, Mingyuan
    Xu, Jin
    MATHEMATICS, 2022, 10 (06)
  • [8] A note on the minimum total coloring of planar graphs
    Hui Juan Wang
    Zhao Yang Luo
    Bin Liu
    Yan Gu
    Hong Wei Gao
    Acta Mathematica Sinica, English Series, 2016, 32 : 967 - 974
  • [9] A Note on the Minimum Total Coloring of Planar Graphs
    Hui Juan WANG
    Zhao Yang LUO
    Bin LIU
    Yan GU
    Hong Wei GAO
    Acta Mathematica Sinica,English Series, 2016, (08) : 967 - 974
  • [10] Total coloring of recursive maximal planar graphs
    Zhou, Yangyang
    Zhao, Dongyang
    Ma, Mingyuan
    Xu, Jin
    THEORETICAL COMPUTER SCIENCE, 2022, 909 : 12 - 18