Strong chromatic index of graphs with maximum degree four

Abstract

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 $Δ$ has a strong edge-coloring using at most $\frac{5}{4}Δ^2$ colors if $Δ$ is even, and at most $\frac{5}{4}Δ^2 - \frac{1}{2}Δ+ \frac{1}{4}$ if $Δ$ is odd. Despite recent progress for large $Δ$ by using an iterative probabilistic argument, the only nontrivial case of the conjecture that has been verified is when $Δ= 3$, leaving the need for new approaches to verify the conjecture for any $Δ\ge 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 Cranston in 2006 and moves closer to the conjectured upper bound of 20.