2018/09/06 by Dai, Tianjiao, Wang, Guanghui, Yang, Donglei +1 · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1809.01805
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 χ's(G), is the minimum k for which G has a strong k-edge-coloring. In 1985, Erdős and Nešetřil conjectured that χ's(G)≤(5)/(4)Δ(G)2, where Δ(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.