List strong edge-coloring of graphs with maximum degree 4

Abstract

A strong edge-coloring of a graph $G$ is an edge-coloring such that any two edges on a path of length three receive distinct colors. We denote the strong chromatic index by ${\chi }_s^{\prime }(G)$ which is the minimum number of colors that allow a strong edge-coloring of $G$. Erdős and Nešetřil conjectured in 1985 that the upper bound of ${\chi }_s^{\prime }(G)$ is $\frac{5}{4}{\Delta }^2$ when $\Delta$ is even and $\frac{1}{4}(5{\Delta }^2-2\Delta +1)$ when $\Delta$ is odd, where $\Delta$ is the maximum degree of $G$. The conjecture is proved right when $\Delta \le 3$. The best known upper bound for $\Delta =4$ is 22 due to Cranston previously. In this paper we extend the result of Cranston to list strong edge-coloring, that is to say, we prove that when $\Delta =4$ the upper bound of list strong chromatic index is 22.

10 pages, 5 figures