Injective choosability of planar graphs of girth five and six

被引:18
作者
Li, Rui [1 ,2 ]
Xu, Baogang [1 ]
机构
[1] Nanjing Normal Univ, Sch Math Sci, Nanjing 210046, Jiangsu, Peoples R China
[2] Shihezi Univ, Normal Coll, Shihezi 832003, Xinjiang, Peoples R China
关键词
Injective coloring; Maximum average degree; Girth; Planar graphs; COLORINGS;
D O I
10.1016/j.disc.2011.10.029
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
An injective k-coloring of a graph G is an assignment of k colors to V (G) such that vertices having a common neighbor receive distinct colors. we study the list version of injective colorings of planar graphs. Let chi(l)(i)(G) and mad(G) be the injective choosability number and the maximum average degree of G, respectively. It is proved that (1) for each graph G with mad(G) < 10/3, chi(l)(i)(G) <= Delta(G) + 4 if Delta(G) >= 30 (this conditionally improves some results of Doyon et al. (2010) [9] and Luzar et al. (2009)[11]). chi(l)(i)(G) <= Delta(G) + 5 if Delta(G) >= 18, and chi(l)(i)(G) <= Delta(G) + 6 if Delta(G) >= 14; (2) chi(l)(i)(G) <= Delta(G) + 2 if mad(G) < 3 and Delta(G) >= 12 (this conditionally improves a result of Doyon et al. (2010) [9]). (C) 2011 Elsevier B.V. All rights reserved.
引用
收藏
页码:1260 / 1265
页数:6
相关论文
共 11 条
[1]  
Bondy J. A., 1976, Graduate Texts in Mathematics, V290
[2]   List injective colorings of planar graphs [J].
Borodin, O. V. ;
Ivanova, A. O. .
DISCRETE MATHEMATICS, 2011, 311 (2-3) :154-165
[3]   2-distance (Δ+2)-coloring of planar graphs with girth six and Δ ≥ 18 [J].
Borodin, O. V. ;
Ivanova, A. O. .
DISCRETE MATHEMATICS, 2009, 309 (23-24) :6496-6502
[4]  
Borodin O.V., 2007, Diskretn. Anal. Issled. Oper., Ser. 1, V14, P13
[5]   List 2-distance (Δ+2)-coloring of planar graphs with girth six [J].
Borodin, Oleg V. ;
Ivanova, Anna O. .
EUROPEAN JOURNAL OF COMBINATORICS, 2009, 30 (05) :1257-1262
[6]   Injective coloring of planar graphs [J].
Bu, Yuehua ;
Chen, Dong ;
Raspaud, Andre ;
Wang, Weifan .
DISCRETE APPLIED MATHEMATICS, 2009, 157 (04) :663-672
[7]   Injective Colorings of Graphs with Low Average Degree [J].
Cranston, Daniel W. ;
Kim, Seog-Jin ;
Yu, Gexin .
ALGORITHMICA, 2011, 60 (03) :553-568
[8]   Injective colorings of sparse graphs [J].
Cranston, Daniel W. ;
Kim, Seog-Jin ;
Yu, Gexin .
DISCRETE MATHEMATICS, 2010, 310 (21) :2965-2973
[9]   Some bounds on the injective chromatic number of graphs [J].
Doyon, Alain ;
Hahn, Gena ;
Raspaud, Andre .
DISCRETE MATHEMATICS, 2010, 310 (03) :585-590
[10]   On the injective chromatic number of graphs [J].
Hahn, G ;
Kratochvíl, J ;
Sirán, J ;
Sotteau, D .
DISCRETE MATHEMATICS, 2002, 256 (1-2) :179-192