Entire coloring of plane graph with maximum degree eleven

被引:1
作者
Dong, Wei [1 ,2 ]
Lin, Wensong [1 ]
机构
[1] Southeast Univ, Dept Math, Nanjing 211189, Jiangsu, Peoples R China
[2] Nanjing Xiaozhuang Univ, Sch Math & Informat Technol, Nanjing 211171, Jiangsu, Peoples R China
基金
中国博士后科学基金;
关键词
Entire coloring; Plane graph; Maximum degree;
D O I
10.1016/j.disc.2014.07.022
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
A plane graph is called entirely k-colorable if for each x is an element of V (G) boolean OR E(G) boolean OR F(G), we can use k colors to assign each element x a color such that any two elements that are adjacent or incident receive distinct colors. In this paper, we prove that if G is a plane graph with Delta = 11, then G is entirely (Delta+2)-colorable, which provides a positive answer to a problem posed by Borodin (Problem 5.2 in Borodin (2013)). (C) 2014 Elsevier B.V. All rights reserved.
引用
收藏
页码:46 / 56
页数:11
相关论文
共 9 条
[1]  
Bondy J.A., 2008, GTM
[2]   Colorings of plane graphs: A survey [J].
Borodin, O. V. .
DISCRETE MATHEMATICS, 2013, 313 (04) :517-539
[3]  
Borodin O.V., 1993, METEM ZAMETKI, V53, P35
[4]  
Kronk H. V., 1973, Discrete Mathematics, V5, P253, DOI 10.1016/0012-365X(73)90142-8
[5]   ENTIRE CHROMATIC NUMBER OF A NORMAL GRAPH IS AT MOST 7 [J].
KRONK, HV ;
MITCHEM, J .
BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1972, 78 (05) :799-&
[6]   On the entire coloring conjecture [J].
Sanders, DP ;
Zhao, Y .
CANADIAN MATHEMATICAL BULLETIN-BULLETIN CANADIEN DE MATHEMATIQUES, 2000, 43 (01) :108-114
[7]   Entire colouring of plane graphs [J].
Wang, Weifan ;
Zhu, Xuding .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2011, 101 (06) :490-501
[8]   Entire (Δ+2)-colorability of plane graphs [J].
Wang, Yingqian .
EUROPEAN JOURNAL OF COMBINATORICS, 2014, 38 :110-121
[9]   Plane Graphs with Maximum Degree 8 Are Entirely (+3)-Colorable [J].
Wang, Yingqian ;
Mao, Xianghua ;
Miao, Zhengke .
JOURNAL OF GRAPH THEORY, 2013, 73 (03) :305-317