Injective edge coloring of sparse graphs

被引:0
作者
Lai, Hong-Jian [1 ,2 ]
Luo, Austin [3 ]
机构
[1] Guangdong Polytech Normal Univ, Sch Math & Syst Sci, Guangzhou 510665, Peoples R China
[2] West Virginia Univ, Sch Math & Data Sci, Morgantown, WV 26506 USA
[3] Morgantown High Sch, Morgantown, WV 26501 USA
关键词
Edge coloring; injective edge coloring; sparse graphs; maximum average degree;
D O I
10.1142/S179383092450112X
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
A k-edge coloring of a graph G is a mapping phi : E(G) ->{1, 2,& mldr;,k}. A k-injective edge coloring is a k-edge coloring such that any two edges e and f with distance exactly 1 or in a triangle receive distinct colors. The injective edge chromatic index of a graph G, denoted by chi(inj)'(G), is the minimum integer k such that G has a k-injective edge coloring. In this paper, we show that chi(inj)'(G) <= max{2 Delta(G) - 2, 6} if mad(G) < (5)/ (2); chi(inj)'(G) <= 2 Delta(G) if mad(G) <( 29)/ (11); and chi(inj)'(G) <= 2 Delta(G) + 1 if mad(G) < (14) /(5). We also show that chi(inj)'(G) <= 4 if G is subcubic and mad(G) < (7)/ (3).
引用
收藏
页数:20
相关论文
共 9 条
[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]   Injective edge-coloring of subcubic graphs [J].
Ferdjallah, Baya ;
Kerdjoudj, Samia ;
Raspaud, Andre .
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2022, 14 (08)
[5]   Complexity and algorithms for injective edge-coloring in graphs [J].
Foucaud, Florent ;
Hocquard, Herve ;
Lajou, Dimitri .
INFORMATION PROCESSING LETTERS, 2021, 170
[6]   Injective edge-coloring of graphs with given maximum degree [J].
Kostochka, Alexandr ;
Raspaud, Andre ;
Xu, Jingwei .
EUROPEAN JOURNAL OF COMBINATORICS, 2021, 96
[7]   List injective edge-coloring of subcubic graphs [J].
Lv, Jian-Bo ;
Li, Jianxi ;
Zhou, Nian Hong .
DISCRETE APPLIED MATHEMATICS, 2021, 302 :163-170
[8]   Note on injective edge-coloring of graphs [J].
Miao, Zhengke ;
Song, Yimin ;
Yu, Gexin .
DISCRETE APPLIED MATHEMATICS, 2022, 310 :65-74
[9]   Injective edge coloring of sparse graphs with maximum degree 5 [J].
Zhu, Junlei ;
Bu, Yuehua ;
Zhu, Hongguo .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2023, 45 (01)