In 1985, Erd\H{ o}s and Ne\'{ s}etril conjectured that the strong edge-coloring number of a graph is bounded above by ${ 5/4}\Delta^2$ when $\Delta$ is even and ${ 1/4}(5\Delta^2-2\Delta+1)$ when $\Delta$ is odd. They gave a simple construction which requires this many colors. The conjecture has been verified for $\Delta\leq 3$. For $\Delta=4$, the conjectured bound is 20. Previously, the best known upper bound was 23 due to Horak. In this paper we give an algorithm that uses at most 22 colors.
Categories: math.CO