2015/10/03 by Zang, Chuanyun
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1510.00785
A strong edge-coloring of a graph G is an edge-coloring such that no two edges of distance at most two receive the same color. The strong chromatic index χ's(G) is the minimum number of colors in a strong edge-coloring of G. P. Erdős and J. Nešetřil conjectured in 1985 that χ's(G) is bounded above by \frac54Δ2 when Δ is even and \frac14(5Δ2-2Δ+1) when Δ is odd, where Δ is the maximum degree of G. In this paper, we give an algorithm that uses at most 2Δ2-3Δ+2 colors for graphs with girth at least 5. And in particular, we prove that any graph with maximum degree Δ=5 has a strong edge-coloring with 37 colors.