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

AbstractIn 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. For Δ=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