Injective edge coloring of sparse graphs with maximum degree 5

被引:7
作者
Zhu, Junlei [1 ]
Bu, Yuehua [2 ,3 ]
Zhu, Hongguo [2 ]
机构
[1] Jiaxing Univ, Coll Data Sci, Jiaxing 314001, Peoples R China
[2] Zhejiang Normal Univ, Dept Math, Jinhua 321004, Zhejiang, Peoples R China
[3] Zhejiang Normal Univ, Xingzhi Coll, Jinhua 321004, Zhejiang, Peoples R China
基金
美国国家科学基金会;
关键词
Maximum degree; Maximum average degree; Injective edge coloring;
D O I
10.1007/s10878-022-00972-w
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
A k-injective-edge coloring of a graph G is a mapping c : E(G)-* {1 , 2 , middot middot middot, k} such that c(e(1)) &NOTEQUexpressionL;c(e(3)) for any three consecutive edges e1 , e2 , e3 of a path or a 3-cycle. chi i(G) = min{k|G has a k-injective-edge coloring} is called the injective chromatic index of G. In this paper, we prove that for graphs G with delta(G) < 5, (1) chi i(G) < 8 if mad(G) < 7/3; (2) chi i(G) < 9 if mad(G) < 12/5; (3) chi i(G) < 10 if mad(G) < 5/2 ; (4) chi i(G) < 11 if mad(G) < 18/7.
引用
收藏
页数:10
相关论文
共 9 条
[1]   Induced and weak induced arboricities [J].
Axenovich, Maria ;
Doerr, Philip ;
Rollin, Jonathan ;
Ueckerdt, Torsten .
DISCRETE MATHEMATICS, 2019, 342 (02) :511-519
[2]  
[卜月华 Bu Yuehua], 2020, [数学进展, Advances in Mathematics (China)], V49, P675
[3]   Injective edge coloring of sparse graphs [J].
Bu, Yuehua ;
Qi, Chentao .
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2018, 10 (02)
[4]   Injective Edge Coloring of Graphs [J].
Cardoso, Domingos M. ;
Cerdeira, J. Orestes ;
Dominic, Charles ;
Cruz, J. Pedro .
FILOMAT, 2019, 33 (19) :6411-6423
[5]  
Ferdjallah B, 2020, INJECTIVE EDGE COLOR, V349
[6]   Complexity and algorithms for injective edge-coloring in graphs [J].
Foucaud, Florent ;
Hocquard, Herve ;
Lajou, Dimitri .
INFORMATION PROCESSING LETTERS, 2021, 170
[7]   Injective edge-coloring of graphs with given maximum degree [J].
Kostochka, Alexandr ;
Raspaud, Andre ;
Xu, Jingwei .
EUROPEAN JOURNAL OF COMBINATORICS, 2021, 96
[8]   List injective edge-coloring of subcubic graphs [J].
Lv, Jian-Bo ;
Li, Jianxi ;
Zhou, Nian Hong .
DISCRETE APPLIED MATHEMATICS, 2021, 302 :163-170
[9]   Note on injective edge-coloring of graphs [J].
Miao, Zhengke ;
Song, Yimin ;
Yu, Gexin .
DISCRETE APPLIED MATHEMATICS, 2022, 310 :65-74