List injective coloring of a class of planar graphs without short cycles

被引:8
作者
Bu, Yuehua [1 ,2 ]
Huang, Chaoyuan [1 ]
机构
[1] Zhejiang Normal Univ, Dept Math, Jinhua 321004, Zhejiang, Peoples R China
[2] Zhejiang Normal Univ, Xingzhi Coll, Jinhua 321004, Zhejiang, Peoples R China
关键词
Planar graph; girth; injective coloring; list coloring;
D O I
10.1142/S1793830918500684
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
An injective k-coloring of a graph G is a mapping c: V (G) -> {1, 2,..., k} such that c(u) does not satisfy c(v) whenever u, v have a common neighbor in G. A list assignment of a graph G is a mapping L that assigns a color list L(v) to each vertex nu V (G). Given a list assignment L of G, an injective coloring phi of G is called an injective L-coloring if phi(nu) is an element of L(nu) for every nu is an element of V (G). In this paper, we show that if G is a planar graph with girth g >= 5, then chi(l)(i) (G) <= Delta(G) + Delta(G) >= 11.
引用
收藏
页数:12
相关论文
共 7 条
[1]   LIST INJECTIVE COLORING OF PLANAR GRAPHS WITH GIRTH g >= 5 [J].
Bu, Yuehua ;
Yang, Sheng .
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2014, 6 (01)
[2]   Injective coloring of planar graphs [J].
Bu, Yuehua ;
Chen, Dong ;
Raspaud, Andre ;
Wang, Weifan .
DISCRETE APPLIED MATHEMATICS, 2009, 157 (04) :663-672
[3]   Injective Colorings of Graphs with Low Average Degree [J].
Cranston, Daniel W. ;
Kim, Seog-Jin ;
Yu, Gexin .
ALGORITHMICA, 2011, 60 (03) :553-568
[4]   Some bounds on the injective chromatic number of graphs [J].
Doyon, Alain ;
Hahn, Gena ;
Raspaud, Andre .
DISCRETE MATHEMATICS, 2010, 310 (03) :585-590
[5]   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
[6]   Injective choosability of planar graphs of girth five and six [J].
Li, Rui ;
Xu, Baogang .
DISCRETE MATHEMATICS, 2012, 312 (06) :1260-1265
[7]  
Yuehua B., 2016, DISCRETE MATH J ZHEJ, V39, P6