2018/01/21 by Zhang, Baochen, Chang, Yulin, Hu, Jie +2
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1801.06758
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 χs'(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 χs'(G) is (5)/(4)Δ2 when Δ is even and (1)/(4)(5Δ2-2Δ+1) when Δ is odd, where Δ is the maximum degree of G. The conjecture is proved right when Δ≤3. The best known upper bound for Δ=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 Δ=4 the upper bound of list strong chromatic index is 22.