×

Injective edge coloring for graphs with small edge weight. (English) Zbl 1497.05094

Summary: An injective \(k\)-edge coloring of a graph \(G=(V(G),E(G))\) is a \(k\)-edge coloring \(\varphi\) such that if \(e_1\) and \(e_2\) are at distance exactly 2 or in the same triangle, then \(\varphi (e_1)\ne \varphi (e_2)\). The injective chromatic index of \(G\), denoted by \(\chi_i'(G)\), is the minimum \(k\) such that \(G\) has an injective \(k\)-edge coloring. The edge weight of \(G\) is defined as \(ew(G)=\max \{d_G(u)+d_G(v):uv\in E(G)\}\). In this paper, we show that \(\chi_i^\prime(G)\le 3\) if \(ew(G)\le 5; \chi_i^\prime(G)\le 7\) if \(ew(G)\le 6\); and \(\chi_i^\prime(G)\le 11\) if \(ew(G)\le 7\).

MSC:

05C15 Coloring of graphs and hypergraphs
05C22 Signed and weighted graphs
Full Text: DOI

References:

[1] Axenovich, M.; Dörr, P.; Rollin, J.; Ueckerdt, T., Induced and weak induced arboricities, Discrete Math., 342, 511-519 (2019) · Zbl 1400.05179 · doi:10.1016/j.disc.2018.10.018
[2] Cardoso, DM; Cerdeira, JO; Cruz, JP; Dominic, C., Injective edge coloring of graphs, Filomat, 33, 6411-6423 (2019) · Zbl 1499.05206 · doi:10.2298/FIL1919411C
[3] Ferdjallah, B., Kerdjoudj, S., Raspaud, A.: Injective edge-coloring of sparse graphs (2020). arXiv:1907.09838v2 [math.CO]
[4] Foucaud, F.; Hocquard, H.; Lajou, D., Complexity and algorithms for injective edge-coloring in graphs, Inf. Process. Lett., 170, 106121 (2021) · Zbl 1516.68060 · doi:10.1016/j.ipl.2021.106121
[5] Kostochka, A.; Raspaud, A.; Xu, JW, Injective edge-coloring of graphs with given maximum degree, Eur. J. Comb., 96, 103355 (2021) · Zbl 1466.05072 · doi:10.1016/j.ejc.2021.103355
[6] Li, Y.; Chen, L., Injective edge coloring of generalized Petersen graphs, AIMS Math., 6, 8, 7929-7943 (2021) · Zbl 1484.05072 · doi:10.3934/math.2021460
[7] Yue, J.; Zhang, SL; Zhang, X., Note on the perfect EIC-graphs, Appl. Math. Comput., 289, 481-485 (2016) · Zbl 1410.05076 · doi:10.1016/j.amc.2016.05.031
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.