Strong edge-coloring of graphs with maximum degree 4 using 22 colors

In 1985, Erdős and Neśetril conjectured that the strong edge-coloring number of a graph is bounded above by 54Δ2 when ΔΔ is even and 14(5Δ2-2Δ+1) when ΔΔ is odd. They gave a simple construction which requires this many colors. The conjecture has been verified for Δ⩽3Δ⩽3. For Δ=4Δ=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.