Injective coloring of plane graphs with girth 5

被引：15
作者：
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
来源：
DISCRETE MATHEMATICS | 2014年 / 315卷
基金：
中国博士后科学基金;
关键词：
Girth; Plane graph; lnjective coloring; Cycle;
D O I：
10.1016/j.disc.2013.10.017
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
An injective coloring of a graph is a vertex coloring where two vertices have distinct colors if a path of length two exists between them. Let G be a plane graph with g(G) >= 5 and chi(i)(G) be the injective chromatic number of G. In this paper, we improve some known results by proving that chi(i)(G) <= Delta + 3 if Delta (G) >= 35 and chi(i)(G) <= Delta + 6 for arbitrary Delta(G). (C) 2013 Elsevier B.V. All rights reserved.
引用
收藏
页码：120 / 127
页数：8
相关论文
共 11 条
[1]  
Bondy J. A., 1976, Graduate Texts in Mathematics, V290
[2]   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
[3]   Injective coloring of planar graphs [J].
Bu, Yuehua ;
Chen, Dong ;
Raspaud, Andre ;
Wang, Weifan .
DISCRETE APPLIED MATHEMATICS, 2009, 157 (04) :663-672
[4]   Injective Colorings of Graphs with Low Average Degree [J].
Cranston, Daniel W. ;
Kim, Seog-Jin ;
Yu, Gexin .
ALGORITHMICA, 2011, 60 (03) :553-568
[5]   Injective colorings of sparse graphs [J].
Cranston, Daniel W. ;
Kim, Seog-Jin ;
Yu, Gexin .
DISCRETE MATHEMATICS, 2010, 310 (21) :2965-2973
[6]   Injective coloring of planar graphs with girth 6 [J].
Dong, Wei ;
Lin, Wensong .
DISCRETE MATHEMATICS, 2013, 313 (12) :1302-1311
[7]  
Doyon A., 2005, PREPRINT
[8]   Some bounds on the injective chromatic number of graphs [J].
Doyon, Alain ;
Hahn, Gena ;
Raspaud, Andre .
DISCRETE MATHEMATICS, 2010, 310 (03) :585-590
[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
12