List injective coloring of planar graphs with girth g ≥ 6

被引：10
作者：
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 [J].
Agnarsson, G ;
Halldórsson, MM .
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 [J].
Borodin, O. V. ;
Ivanova, A. O. .
SIBERIAN MATHEMATICAL JOURNAL, 2011, 52 (01) :23-29
[5]   List injective colorings of planar graphs [J].
Borodin, O. V. ;
Ivanova, A. O. .
DISCRETE MATHEMATICS, 2011, 311 (2-3) :154-165
[6]   2-distance (Δ+2)-coloring of planar graphs with girth six and Δ ≥ 18 [J].
Borodin, O. V. ;
Ivanova, A. O. .
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 [J].
Borodin, Oleg V. ;
Ivanova, Anna O. .
EUROPEAN JOURNAL OF COMBINATORICS, 2009, 30 (05) :1257-1262
[10]  
Borodin Oleg V., 2004, SIB ELEKT MAT IZV, V1, P76
123