Injective coloring of planar graphs with girth 6

被引：30

作者：

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 | 2013年 / 313卷 / 12期

关键词：

Girth; Planar graph; Injective coloring; Cycle;

D O I：

10.1016/j.disc.2013.02.014

中图分类号：

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 chi(i)(G) be the injective chromatic number of a graph G. In this paper, we investigate the injective coloring of planar graphs with girth 6. We improve some results of Borodin and Ivanova (2011) [1], Doyon et al. (2010) [4] and Li and Xu (2012) [6] by showing that if G is a planar graph with girth at least 6, then (1) chi(i)(G) <= Delta + 3; (2) chi(i)(G) <= Delta + 2 if Delta >= 9; (3) chi(i)(G) <= Delta + 1 if Delta >= 17. (c) 2013 Elsevier B.V. All rights reserved.

引用

页码：1302 / 1311

页数：10

共 7 条

[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] Injective coloring of planar graphs [J].

Bu, Yuehua ;

Chen, Dong ;

Raspaud, Andre ;

Wang, Weifan .

DISCRETE APPLIED MATHEMATICS, 2009, 157 (04) :663-672

[3] Some results on the injective chromatic number of graphs [J].

Chen, Min ;

Hahn, Gena ;

Raspaud, Andre ;

Wang, Weifan .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2012, 24 (03) :299-318

[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] Injective colorings of planar graphs with few colors [J].

Luzar, Borut ;

Skrekovski, Riste ;

Tancer, Martin .

DISCRETE MATHEMATICS, 2009, 309 (18) :5636-5649

← 1 →