A smaller upper bound for the list injective chromatic number of planar graphs

被引:0
|
作者
Chen, Hongyu [1 ]
Zhang, Li [2 ]
机构
[1] Shanghai Inst Technol, Sch Sci, Shanghai 201418, Peoples R China
[2] Shanghai Lixin Univ Accounting & Finance, Sch Stat & Math, Shanghai 201209, Peoples R China
来源
AIMS MATHEMATICS | 2025年 / 10卷 / 01期
关键词
list injective coloring; maximum degree; girth; planar graph; GIRTH;
D O I
10.3934/math.2025014
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
An injective vertex coloring of a graph G is a coloring where no two vertices that share a common neighbor are assigned the same color. If for any list L of permissible colors with size k assigned to the vertices V ( G ) of a graph G , there exists an injective coloring phi in which phi ( v ) E L ( v ) for each vertex v E V ( G ), then G is said to be injectively k-choosable. The notation chi l i ( G ) represents the minimum value of k such that a graph G is injectively k-choosable. In this article, for any maximum degree O , we demonstrate that chi l i ( G ) <= O + 4 if G is a planar graph with girth g >= 5 and without intersecting 5-cycles.
引用
收藏
页码:289 / 310
页数:22
相关论文
共 50 条
  • [21] The r-acyclic chromatic number of planar graphs
    Wang, Guanghui
    Yan, Guiying
    Yu, Jiguo
    Zhang, Xin
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2015, 29 (04) : 713 - 722
  • [22] Girth and fractional chromatic number of planar graphs
    Pirnazar, A
    Ullman, DH
    JOURNAL OF GRAPH THEORY, 2002, 39 (03) : 201 - 217
  • [23] Injective coloring of planar graphs
    Bu, Yuehua
    Chen, Dong
    Raspaud, Andre
    Wang, Weifan
    DISCRETE APPLIED MATHEMATICS, 2009, 157 (04) : 663 - 672
  • [24] Injective coloring of planar graphs
    Yuehua, Bu
    Chentao, Qi
    Junlei, Zhu
    Ting, Xu
    THEORETICAL COMPUTER SCIENCE, 2021, 857 : 114 - 122
  • [25] The list chromatic numbers of some planar graphs
    Enyue L.
    Kemin Z.
    Applied Mathematics-A Journal of Chinese Universities, 1999, 14 (1) : 108 - 116
  • [26] A bound for the game chromatic number of graphs
    Dinski, T
    Zhu, XD
    DISCRETE MATHEMATICS, 1999, 196 (1-3) : 109 - 115
  • [27] An improved upper bound on the adjacent vertex distinguishing total chromatic number of graphs
    Vuckovic, Bojan
    DISCRETE MATHEMATICS, 2018, 341 (05) : 1472 - 1478
  • [28] A Bound on the Chromatic Number of an Almost Planar Graph
    Nenashev G.V.
    Journal of Mathematical Sciences, 2014, 196 (6) : 784 - 790
  • [29] Injective-edge-coloring of planar graphs with girth restriction
    Bu, Yuehua
    Wang, Peng
    Zhu, Hongguo
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2024, 16 (05)
  • [30] On the list injective coloring of planar graphs without a 4--cycle intersecting with a 5--cycle
    Bu, Yuehua
    Zheng, Hongrui
    Zhu, Hongguo
    AIMS MATHEMATICS, 2025, 10 (01): : 1814 - 1825