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

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^{\mathrm{\prime }}(G)$ is the minimum number of colors in a strong edge-coloring of $G$. P. Erd\H{o}s and J. Ne\v{s}et\v{r}il conjectured in 1985 that ${\chi }_s^{\mathrm{\prime }}(G)$ is bounded above by $\frac{5}{4}{\mathrm{\Delta }}^2$ when $\mathrm{\Delta }$ is even and $\frac{1}{4}(5{\mathrm{\Delta }}^2-2\mathrm{\Delta }+1)$ when $\mathrm{\Delta }$ is odd, where $\mathrm{\Delta }$ is the maximum degree of $G$. In this paper, we give an algorithm that uses at most $2{\mathrm{\Delta }}^2-3\mathrm{\Delta }+2$ colors for graphs with girth at least $5$. And in particular, we prove that any graph with maximum degree $\mathrm{\Delta }=5$ has a strong edge-coloring with $37$ colors.