PreprintarXiv licencearXiv
A note on the injective edge coloring of graphs with bounded maximum degree
Abstract
Let G be a graph. Under an \emph{injective edge coloring} of G, any two edges at distance $2$ or belonging to a common triangle receive distinct colors. The \emph{injective chromatic index} of G, denoted by χ'inj(G), is the smallest integer k such that G admits an injective edge coloring with k colors. Let Δ be the maximum degree of G. Ferdjallah et al.~proved that χ'inj(G) ≤ 2(Δ−1)2. In this paper, we improve this bound by proving that χ'inj(G) ≤ 2(Δ− 1)2 −Δ+ 3 if Δ≥ 4.
Related
- Strong edge coloring of graphs with maximum degree $6$
- Total-coloring of planar graphs with maximum degree 6 and without prescribed 4-cycles
- Frugal coloring in planar graphs with maximum degree 4 and 5
- Sharp lower bounds for bisections of graphs with bounded maximum degree
- Approximation Algorithms for Maximum-Weight Degree-Bounded Forests
BibTeX
@misc{tian2026note,
title = {{A note on the injective edge coloring of graphs with bounded maximum degree}},
author = {Lin Tian and Runze Wang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.04891},
eprint = {2610.04891},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.04891},
}
RIS
TY - UNPB
TI - A note on the injective edge coloring of graphs with bounded maximum degree
AU - Lin Tian
AU - Runze Wang
PY - 2026
DA - 2026/10/04
PB - arXiv
DO - 10.48550/arxiv.2610.04891
UR - https://arxiv.org/abs/2610.04891
AB - Let G be a graph. Under an \emph{injective edge coloring} of G, any two edges at distance $2$ or belonging to a common triangle receive distinct colors. The \emph{injective chromatic index} of G, denoted by χ'_inj(G), is the smallest integer k such that G admits an injective edge coloring with k colors. Let Δ be the maximum degree of G. Ferdjallah et al.~proved that χ'_inj(G) ≤ 2(Δ−1)^2. In this paper, we improve this bound by proving that χ'_inj(G) ≤ 2(Δ− 1)^2 −Δ+ 3 if Δ≥ 4.
ER -