List injective Coloring of Planar Graphs

被引:0
作者
Bu, Yuehua [1 ,2 ]
Wang, Chao [1 ]
Yang, Sheng [1 ]
机构
[1] Zhejiang Normal Univ, Dept Math, Jinhua 321004, Peoples R China
[2] Zhejiang Normal Univ, Xingzhi Coll, Jinhua 321004, Peoples R China
关键词
Planar graph; Cycle; Grith; List injective coloring; GIRTH; 6;
D O I
暂无
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
An injective k-coloring of graph G is a mapping c : V(G) -> {1,2, . . . , k}, such that c(u) not equal c(v) for any two vertices u, v is an element of V(G), whenever u, v have a common neighbor. If G has an injective k-coloring, then we call that G is injective k-colorable. Let chi(i)(G) = min{k vertical bar G is injective k-colorable} be the chromatic number of G. Assign each vertex v is an element of V(G) a coloring set L(v), then L = {L(v)vertical bar v is an element of V(G)} is said to be a color list of G. Let L he a color list of G, if G has an injective coloring c such that c(v) is an element of L(v), for all v is an element of V(G), then we call c is an injective L-coloring of G. If for any color list L, such that vertical bar L(v)vertical bar >= k, G has an injective L-coloring, then G is said to he injective k-choosable. Let chi(l)(i)(G) = min{k vertical bar G is injective k-choosable} be the injective chromatic number of G. In this paper, we prove if G is a planar graph without 3,4,6-cycles and Delta(G) >= 15, then chi(l)(i)(G) <= Delta + 2; If G is a planar graph with g(G) >= 5 and Delta >= 10, then chi(l)(i)(G) <= Delta + 5.
引用
收藏
页码:191 / 211
页数:21
相关论文
共 11 条
[1]   Injective (Δ+1)-coloring of planar graphs with girth 6 [J].
Borodin, O. V. ;
Ivanova, A. O. .
SIBERIAN MATHEMATICAL JOURNAL, 2011, 52 (01) :23-29
[2]   List injective colorings of planar graphs [J].
Borodin, O. V. ;
Ivanova, A. O. .
DISCRETE MATHEMATICS, 2011, 311 (2-3) :154-165
[3]   List injective coloring of planar graphs with girth 5, 6, 8 [J].
Bu, Yuehua ;
Lu, Kai .
DISCRETE APPLIED MATHEMATICS, 2013, 161 (10-11) :1367-1377
[4]   Injective coloring of planar graphs [J].
Bu, Yuehua ;
Chen, Dong ;
Raspaud, Andre ;
Wang, Weifan .
DISCRETE APPLIED MATHEMATICS, 2009, 157 (04) :663-672
[5]   Injective Colorings of Graphs with Low Average Degree [J].
Cranston, Daniel W. ;
Kim, Seog-Jin ;
Yu, Gexin .
ALGORITHMICA, 2011, 60 (03) :553-568
[6]   Injective colorings of sparse graphs [J].
Cranston, Daniel W. ;
Kim, Seog-Jin ;
Yu, Gexin .
DISCRETE MATHEMATICS, 2010, 310 (21) :2965-2973
[7]  
Dimitrov D., 2009, INJECTIVE COLO UNPUB
[8]   Injective coloring of planar graphs with girth 6 [J].
Dong, Wei ;
Lin, Wensong .
DISCRETE MATHEMATICS, 2013, 313 (12) :1302-1311
[9]   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
[10]   Injective choosability of planar graphs of girth five and six [J].
Li, Rui ;
Xu, Baogang .
DISCRETE MATHEMATICS, 2012, 312 (06) :1260-1265