List injective coloring of planar graphs with girth g ≥ 6

被引：9

作者：

Chen, Hong-Yu ^{[1
]}

Wu, Jian-Liang ^{[2
]}

机构：

[1] Shanghai Inst Technol, Sch Sci, Shanghai 201418, Peoples R China

[2] Shandong Univ, Sch Math, Jinan 250100, Shandong, Peoples R China

来源：

DISCRETE MATHEMATICS | 2016年 / 339卷 / 12期

关键词：

Planar graph; List injective coloring; Girth; CHROMATIC NUMBER;

D O I：

10.1016/j.disc.2016.06.017

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A vertex coloring of a graph G is called injective if any two vertices with a common neighbor receive distinct colors. A graph G is injectively k-choosable if any list L of admissible colors on V(G) of size k allows an injective coloring phi such that phi(v) is an element of L(v) whenever v is an element of V(G). The least k for which G is injectively k-choosable is denoted by chi(1)(i)(G). In this paper, we show that if G is a planar graph with girth g >= 6, then chi(1)(i)(G) <= Delta + 3. (C) 2016 Elsevier B.V. All rights reserved.

引用

页码：3043 / 3051

页数：9

共 29 条

[1] Coloring powers of planar graphs
Agnarsson, G
Halldórsson, MM
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2003, 16 (04) : 651 - 662
[2] Agnarsson G, 2000, PROCEEDINGS OF THE ELEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P654
[3] Borodin OV, 2006, SIB ELECTRON MATH RE, V3, P441
[4] Injective (Δ+1)-coloring of planar graphs with girth 6
Borodin, O. V.
Ivanova, A. O.
[J]. SIBERIAN MATHEMATICAL JOURNAL, 2011, 52 (01) : 23 - 29
[5] List injective colorings of planar graphs
Borodin, O. V.
Ivanova, A. O.
[J]. DISCRETE MATHEMATICS, 2011, 311 (2-3) : 154 - 165
[6] 2-distance (Δ+2)-coloring of planar graphs with girth six and Δ ≥ 18
Borodin, O. V.
Ivanova, A. O.
[J]. DISCRETE MATHEMATICS, 2009, 309 (23-24) : 6496 - 6502
[7] Borodin O.V., 2009, SIB MAT ZH, V6, P1216
[8] Borodin O.V., 2005, DISKRETN ANAL ISSLED, V12, P32
[9] List 2-distance (Δ+2)-coloring of planar graphs with girth six
Borodin, Oleg V.
Ivanova, Anna O.
[J]. EUROPEAN JOURNAL OF COMBINATORICS, 2009, 30 (05) : 1257 - 1262
[10] Borodin Oleg V., 2004, SIB ELEKT MAT IZV, V1, P76

← 1 2 3 →