Note on injective edge-coloring of graphs

被引:19
作者
Miao, Zhengke [1 ]
Song, Yimin [2 ]
Yu, Gexin [3 ]
机构
[1] Jiangsu Normal Univ, Sch Math & Stat, Xuzhou, Jiangsu, Peoples R China
[2] Anhui Univ, Sch Math Sci, Hefei, Peoples R China
[3] William & Mary, Dept Math, Williamsburg, VA USA
关键词
Injective edge-coloring; k-degenerate graphs; Maximum average degree; STRONG CHROMATIC INDEX;
D O I
10.1016/j.dam.2021.12.021
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
An injective edge-coloring of graph G is an edge-coloring phi such that phi(e(1)) not equal (e(3)) for any three consecutive edges e(1), e(2) and e(3) of a path or a 3-cycle. Note that such an edge-coloring is not necessarily proper. The minimum number of colors required for an injective edge-coloring is called the injective chromatic index of G, denoted by chi(i)'(G). For every integer k >= 2, we show that every k-degenerate graph G with maximum degree Delta satisfies chi(i)'(G) <= (4k- 3)Delta - 2k(2) - k+3. We also prove that every graph G with Delta = 4, it is injective 9-edge-colorable when its maximum average degree mad(G) < 14/5, injective 10-edge-colorable when mad(G) < 3, injective 11-edge-colorable when mad(G) < 19/6, and injective 12-edge-colorable when mad(G) < 36/11. (C) 2021 Elsevier B.V. All rights reserved.
引用
收藏
页码:65 / 74
页数:10
相关论文
共 8 条
[1]   Induced and weak induced arboricities [J].
Axenovich, Maria ;
Doerr, Philip ;
Rollin, Jonathan ;
Ueckerdt, Torsten .
DISCRETE MATHEMATICS, 2019, 342 (02) :511-519
[2]   Injective edge coloring of sparse graphs [J].
Bu, Yuehua ;
Qi, Chentao .
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2018, 10 (02)
[3]   Injective Edge Coloring of Graphs [J].
Cardoso, Domingos M. ;
Cerdeira, J. Orestes ;
Dominic, Charles ;
Cruz, J. Pedro .
FILOMAT, 2019, 33 (19) :6411-6423
[4]   Strong Chromatic Index of 2-Degenerate Graphs [J].
Chang, Gerard Jennhwa ;
Narayanan, N. .
JOURNAL OF GRAPH THEORY, 2013, 73 (02) :119-126
[5]  
Ferdjallah B, 2020, Arxiv, DOI arXiv:1907.09838
[6]   Injective edge-coloring of graphs with given maximum degree [J].
Kostochka, Alexandr ;
Raspaud, Andre ;
Xu, Jingwei .
EUROPEAN JOURNAL OF COMBINATORICS, 2021, 96
[7]   Strong chromatic index of k-degenerate graphs [J].
Wang, Tao .
DISCRETE MATHEMATICS, 2014, 330 :17-19
[8]  
Yu GX, 2015, GRAPH COMBINATOR, V31, P1815, DOI 10.1007/s00373-014-1478-1