The Strong Chromatic Index of graphs with maximum degree $\Delta$

Abstract

A strong edge-coloring of a graph $G$ is an edge-coloring such that no two edges of distance at most two receive the same color. The strong chromatic index ${\chi }_s^{\prime }(G)$ is the minimum number of colors in a strong edge-coloring of $G$. P. Erdős and J. Nešetřil conjectured in 1985 that ${\chi }_s^{\prime }(G)$ is bounded above by $\frac{5}{4}{\Delta }^2$ when $\Delta$ is even and $\frac{1}{4}(5{\Delta }^2-2\Delta +1)$ when $\Delta$ is odd, where $\Delta$ is the maximum degree of $G$. In this paper, we give an algorithm that uses at most $2{\Delta }^2-3\Delta +2$ colors for graphs with girth at least $5$. And in particular, we prove that any graph with maximum degree $\Delta =5$ has a strong edge-coloring with $37$ colors.