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 条
  • [41] Fractional DP-chromatic number of planar graphs of large girth
    Wu, Jianglin
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2022, 14 (02)
  • [42] Acyclic chromatic indices of planar graphs with girth at least five
    Qiaojun Shu
    Weifan Wang
    Journal of Combinatorial Optimization, 2012, 23 : 140 - 157
  • [43] Acyclic Chromatic Indices of Planar Graphs with Girth At Least 4
    Shu, Qiaojun
    Wang, Weifan
    Wang, Yiqiao
    JOURNAL OF GRAPH THEORY, 2013, 73 (04) : 386 - 399
  • [44] Injective (Δ + 1)-coloring of planar graphs with girth 6
    O. V. Borodin
    A. O. Ivanova
    Siberian Mathematical Journal, 2011, 52 : 23 - 29
  • [45] Acyclic chromatic indices of planar graphs with girth at least five
    Shu, Qiaojun
    Wang, Weifan
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2012, 23 (01) : 140 - 157
  • [46] An improved upper bound for the bondage number of graphs on surfaces
    Huang, Jia
    DISCRETE MATHEMATICS, 2012, 312 (18) : 2776 - 2781
  • [47] Injective (Δ+1)-coloring of planar graphs with girth 6
    Borodin, O. V.
    Ivanova, A. O.
    SIBERIAN MATHEMATICAL JOURNAL, 2011, 52 (01) : 23 - 29
  • [48] Injective chromatic index of sparse graphs
    Bu, Yuehua
    Wang, Peng
    Zhu, Hongguo
    Zhu, Junlei
    DISCRETE APPLIED MATHEMATICS, 2024, 345 : 9 - 16
  • [49] List r-hued chromatic number of graphs with bounded maximum average degrees
    Song, Huimin
    Lai, Hong-Jian
    Wu, Jianliang
    DISCRETE MATHEMATICS, 2018, 341 (05) : 1244 - 1252
  • [50] Neighbor sum distinguishing total chromatic number of planar graphs
    Xu, Changqing
    Li, Jianguo
    Ge, Shan
    APPLIED MATHEMATICS AND COMPUTATION, 2018, 332 : 189 - 196