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 条
[31]   Looseness of Plane Graphs [J].
Czap, Julius ;
Jendrol, Stanislav ;
Kardos, Frantisek ;
Miskuf, Jozef .
GRAPHS AND COMBINATORICS, 2011, 27 (01) :73-85
[32]   Looseness of Plane Graphs [J].
Július Czap ;
Stanislav Jendrol’ ;
František Kardoš ;
Jozef Miškuf .
Graphs and Combinatorics, 2011, 27 :73-85
[33]   Alternating plane graphs [J].
Althoefer, Ingo ;
Haugland, Jan Kristian ;
Scherer, Karl ;
Schneider, Frank ;
Van Cleemput, Nico .
ARS MATHEMATICA CONTEMPORANEA, 2015, 8 (02) :337-363
[34]   The adjacent vertex distinguishing edge choosability of planar graphs with maximum degree at least 11 [J].
Cheng, Xiaohan ;
Wang, Bin ;
Wang, Jihui .
DISCRETE APPLIED MATHEMATICS, 2022, 313 :29-39
[35]   The adjacent vertex distinguishing total choosability of planar graphs with maximum degree at least eleven [J].
Xiaohan Cheng ;
Jianliang Wu .
Journal of Combinatorial Optimization, 2018, 35 :1-13
[36]   The adjacent vertex distinguishing total choosability of planar graphs with maximum degree at least eleven [J].
Cheng, Xiaohan ;
Wu, Jianliang .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2018, 35 (01) :1-13
[37]   Plane graphs with Δ=7 are entirely 10-colorable [J].
Kong, Jiangxu ;
Hu, Xiaoxue ;
Wang, Yiqiao .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2020, 40 (01) :1-20
[38]   Edge looseness of plane graphs [J].
Czap, Julius .
ARS MATHEMATICA CONTEMPORANEA, 2015, 9 (02) :279-286
[39]   Algorithms for drawing plane graphs [J].
Nishizeki, T ;
Miura, K ;
Rahman, S .
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2004, E87D (02) :281-289
[40]   Colorings of plane graphs: A survey [J].
Borodin, O. V. .
DISCRETE MATHEMATICS, 2013, 313 (04) :517-539