Strong list-chromatic index of subcubic graphs

Abstract

A strong $k$-edge-coloring of a graph G is an edge-coloring with $k$ colors in which every color class is an induced matching. The strong chromatic index of $G$, denoted by ${\chi }_s^{\prime }(G)$, is the minimum $k$ for which $G$ has a strong $k$-edge-coloring. In 1985, Erdős and Nešetřil conjectured that ${\chi }_s^{\prime }(G)\le \frac{5}{4}\Delta (G{)}^2$, where $\Delta (G)$ is the maximum degree of $G$. When $G$ is a graph with maximum degree at most 3, the conjecture was verified independently by Andersen and Horák, Qing, and Trotter. In this paper, we consider the list version of strong edge-coloring. In particular, we show that every subcubic graph has strong list-chromatic index at most 11 and every planar subcubic graph has strong list-chromatic index at most 10.

11 pages, 3 figures