Strong edge-coloring of sparse graphs with Ore-degree 7 or 8

Abstract

In a strong edge-coloring of a graph $G=(V,E)$, any two edges of distance at most $2$ get distinct colors. The strong chromatic index of $G$, denoted by ${\chi }_s^{\prime }(G)$, is the minimum number of colors needed in a strong edge-coloring of $G$. The Ore-degree of $G$ is defined by $\max \{d(u)+d(v):uv\in E\}$. In this paper, we apply the discharging method and make use of Hall's marriage theorem to prove two results toward a conjecture by Chen et al. First, we prove that if $G$ is a graph with Ore-degree $7$ and maximum average degree less than $\frac{34}{11}$, then ${\chi }_s^{\prime }(G)\le 13$. This result improves the previous best bound from $\frac{40}{13}$ to $\frac{34}{11}$. Second, we prove that if $G$ is a graph with Ore-degree $8$ and maximum average degree less than $\frac{113}{31}$, then ${\chi }_s^{\prime }(G)\le 20$.

arXiv commentTheorem 1.3 in this paper strengthens the main result in arXiv:2505.20345, which has been published