List injective coloring of a class of planar graphs without short cycles

被引:8
作者
Bu, Yuehua [1 ,2 ]
Huang, Chaoyuan [1 ]
机构
[1] Zhejiang Normal Univ, Dept Math, Jinhua 321004, Zhejiang, Peoples R China
[2] Zhejiang Normal Univ, Xingzhi Coll, Jinhua 321004, Zhejiang, Peoples R China
关键词
Planar graph; girth; injective coloring; list coloring;
D O I
10.1142/S1793830918500684
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
An injective k-coloring of a graph G is a mapping c: V (G) -> {1, 2,..., k} such that c(u) does not satisfy c(v) whenever u, v have a common neighbor in G. A list assignment of a graph G is a mapping L that assigns a color list L(v) to each vertex nu V (G). Given a list assignment L of G, an injective coloring phi of G is called an injective L-coloring if phi(nu) is an element of L(nu) for every nu is an element of V (G). In this paper, we show that if G is a planar graph with girth g >= 5, then chi(l)(i) (G) <= Delta(G) + Delta(G) >= 11.
引用
收藏
页数:12
相关论文
共 7 条
  • [1] LIST INJECTIVE COLORING OF PLANAR GRAPHS WITH GIRTH g >= 5
    Bu, Yuehua
    Yang, Sheng
    [J]. DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2014, 6 (01)
  • [2] Injective coloring of planar graphs
    Bu, Yuehua
    Chen, Dong
    Raspaud, Andre
    Wang, Weifan
    [J]. DISCRETE APPLIED MATHEMATICS, 2009, 157 (04) : 663 - 672
  • [3] Injective Colorings of Graphs with Low Average Degree
    Cranston, Daniel W.
    Kim, Seog-Jin
    Yu, Gexin
    [J]. ALGORITHMICA, 2011, 60 (03) : 553 - 568
  • [4] Some bounds on the injective chromatic number of graphs
    Doyon, Alain
    Hahn, Gena
    Raspaud, Andre
    [J]. DISCRETE MATHEMATICS, 2010, 310 (03) : 585 - 590
  • [5] On the injective chromatic number of graphs
    Hahn, G
    Kratochvíl, J
    Sirán, J
    Sotteau, D
    [J]. DISCRETE MATHEMATICS, 2002, 256 (1-2) : 179 - 192
  • [6] Injective choosability of planar graphs of girth five and six
    Li, Rui
    Xu, Baogang
    [J]. DISCRETE MATHEMATICS, 2012, 312 (06) : 1260 - 1265
  • [7] Yuehua B., 2016, DISCRETE MATH J ZHEJ, V39, P6