The Strong Chromatic Index of graphs with maximum degree $\Delta$
Chuanyun Zang · arXiv (Cornell University) · 2015
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(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(G)$ is bounded above by $\frac54\Delta^2$ when $\Delta$ is even and $\frac14(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.