The entire choosability of plane graphs

被引:0
作者
Weifan Wang
Tingting Wu
Xiaoxue Hu
Yiqiao Wang
机构
[1] Zhejiang Normal University,Department of Mathematics
[2] Beijing University of Chinese Medicine,School of Management
来源
Journal of Combinatorial Optimization | 2016年 / 31卷
关键词
Plane graph; Entire choosability; Maximum degree;
D O I
暂无
中图分类号
学科分类号
摘要
A plane graph G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G$$\end{document} is entirely k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-choosable if, for every list L\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L$$\end{document} of colors satisfying L(x)=k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L(x)=k$$\end{document} for all x∈V(G)∪E(G)∪F(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x\in V(G)\cup E(G) \cup F(G)$$\end{document}, there exists a coloring which assigns to each vertex, each edge and each face a color from its list so that any adjacent or incident elements receive different colors. In 1993, Borodin proved that every plane graph G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G$$\end{document} with maximum degree Δ≥12\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta \ge 12$$\end{document} is entirely (Δ+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}-choosable. In this paper, we improve this result by replacing 12 by 10.
引用
收藏
页码:1221 / 1240
页数:19
相关论文
共 50 条
[21]   PLANE GRAPHS ARE ENTIRELY (Delta+ 5)-CHOOSABLE [J].
Hu, Xiaoxue ;
Wang, Yiqiao .
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2014, 6 (02)
[22]   Entire coloring of plane graph with maximum degree eleven [J].
Dong, Wei ;
Lin, Wensong .
DISCRETE MATHEMATICS, 2014, 336 :46-56
[23]   Note on 3-choosability of planar graphs with maximum degree 4 [J].
Dross, Francois ;
Luzar, Borut ;
Macekova, Maria ;
Sotak, Roman .
DISCRETE MATHEMATICS, 2019, 342 (11) :3123-3129
[24]   Edge choosability of planar graphs without 5-cycles with a chord [J].
Chen, Yongzhu ;
Zhu, Weiyi ;
Wang, Weifan .
DISCRETE MATHEMATICS, 2009, 309 (08) :2233-2238
[25]   Edge choosablity and total choosability of toroidal graphs without intersecting triangles [J].
Li, Rui ;
Xu, Baogang .
ARS COMBINATORIA, 2012, 103 :109-118
[26]   2-Distance choosability of planar graphs with a restriction for maximum degree [J].
Yu, Jiahao ;
Chen, Min ;
Wang, Weifan .
APPLIED MATHEMATICS AND COMPUTATION, 2023, 448
[27]   NEIGHBOR SUM DISTINGUISHING TOTAL CHOOSABILITY OF IC-PLANAR GRAPHS [J].
Song, Wen-Yao ;
Miao, Lian-Ying ;
Duan, Yuan-Yuan .
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2020, 40 (01) :331-344
[28]   Plane graphs with maximum degree 9 are entirely 11-choosable [J].
Hu, Xiaoxue ;
Wang, Weifan ;
Shiu, Wai Chee ;
Wang, Yiqiao .
DISCRETE MATHEMATICS, 2016, 339 (11) :2742-2753
[29]   A note on acyclic total coloring of plane graphs [J].
Dong, Wei .
ARS COMBINATORIA, 2016, 129 :123-137
[30]   Looseness of Plane Graphs [J].
Czap, Julius ;
Jendrol, Stanislav ;
Kardos, Frantisek ;
Miskuf, Jozef .
GRAPHS AND COMBINATORICS, 2011, 27 (01) :73-85