Strong chromatic index of graphs with maximum degree four (Q1671652)

Summary: A strong edge-coloring of a graph \(G\) is a coloring of the edges such that every color class induces a matching in \(G\). The strong chromatic index of a graph is the minimum number of colors needed in a strong edge-coloring of the graph. In 1985, Erdős and Nešetřil conjectured that every graph with maximum degree \(\Delta\) has a strong edge-coloring using at most \(\frac{5}{4}\Delta^2\) colors if \(\Delta\) is even, and at most \(\frac{5}{4}\Delta^2-\frac{1}{2}\Delta + \frac{1}{4}\) if \(\Delta\) is odd. Despite recent progress for large \(\Delta\) by using an iterative probabilistic argument, the only nontrivial case of the conjecture that has been verified is when \(\Delta = 3\), leaving the need for new approaches to verify the conjecture for any \(\Delta\geq 4\). In this paper, we apply some ideas used in previous results to an upper bound of 21 for graphs with maximum degree 4, which improves a previous bound due to \textit{D. W. Cranston} [Discrete Math. 306, No. 21, 2772--2778 (2006; Zbl 1143.05025)] and moves closer to the conjectured upper bound of 20.