LIST INJECTIVE COLORING OF PLANAR GRAPHS WITH GIRTH AT LEAST FIVE

被引:1
作者
Chen, Hongyu [1 ]
机构
[1] Shanghai Inst Technol, Sch Sci, Shanghai 201418, Peoples R China
关键词
Planar graph; list injective coloring; girth;
D O I
10.4134/BKMS.b230097
中图分类号
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(l)(i) (G). For a planar graph G, Bu et al. proved that chi(l)(i)(G) < Delta + 6 if girth g >= 5 and maximum degree Delta(G) >= 8. In this paper, we improve this result by showing that chi li(G) < Delta + 6 for g >= 5 and arbitrary Delta(G).
引用
收藏
页码:263 / 271
页数:9
相关论文
共 19 条
  • [1] [Anonymous], 2010, IMFM Preprint Series, V48, P1110
  • [2] List injective colorings of planar graphs
    Borodin, O. V.
    Ivanova, A. O.
    [J]. DISCRETE MATHEMATICS, 2011, 311 (2-3) : 154 - 165
  • [3] Bu YH, 2018, ARS COMBINATORIA, V141, P191
  • [4] List injective coloring of a class of planar graphs without short cycles
    Bu, Yuehua
    Huang, Chaoyuan
    [J]. DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2018, 10 (05)
  • [5] LIST INJECTIVE COLORING OF PLANAR GRAPHS WITH GIRTH g >= 5
    Bu, Yuehua
    Yang, Sheng
    [J]. DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2014, 6 (01)
  • [6] INJECTIVE COLORING OF PLANAR GRAPHS WITH GIRTH 7
    Bu, Yuehua
    Lu, Kai
    [J]. DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2012, 4 (02)
  • [7] List injective coloring of planar graphs with girth 5, 6, 8
    Bu, Yuehua
    Lu, Kai
    [J]. DISCRETE APPLIED MATHEMATICS, 2013, 161 (10-11) : 1367 - 1377
  • [8] Injective coloring of planar graphs
    Bu, Yuehua
    Chen, Dong
    Raspaud, Andre
    Wang, Weifan
    [J]. DISCRETE APPLIED MATHEMATICS, 2009, 157 (04) : 663 - 672
  • [9] List injective coloring of planar graphs with girth g ≥ 6
    Chen, Hong-Yu
    Wu, Jian-Liang
    [J]. DISCRETE MATHEMATICS, 2016, 339 (12) : 3043 - 3051
  • [10] Injective Colorings of Graphs with Low Average Degree
    Cranston, Daniel W.
    Kim, Seog-Jin
    Yu, Gexin
    [J]. ALGORITHMICA, 2011, 60 (03) : 553 - 568