Strong Chromatic Index of Sparse Graphs

A coloring of the edges of a graph G is strong if each color class is an induced matching of G . The strong chromatic index of G , denoted byχ s ′ ( G ) , is the least number of colors in a strong edge coloring of G . Chang and Narayanan (J Graph Theory 73(2) (2013), 119–126) proved recently thatχ s ′ ( G ) ≤ 10 Δ − 10 for a 2‐degenerate graph G . They also conjectured that for any k ‐degenerate graph G there is a linear boundχ s ′ ( G ) ≤ c k 2 Δ , where c is an absolute constant. This conjecture is confirmed by the following three papers: in (G. Yu, Graphs Combin 31 (2015), 1815–1818), Yu showed thatχ s ′ ( G ) ≤ ( 4 k − 2 ) Δ − k ( 2 k − 1 ) + 1 . In (M. Debski, J. Grytczuk, M. Sleszynska‐Nowak, Inf Process Lett 115(2) (2015), 326–330), Dȩbski, Grytczuk, and Śleszyńska‐Nowak showed thatχ s ′ ( G ) ≤ ( 4 k − 1 ) Δ − k ( 2 k + 1 ) + 1 . In (T. Wang, Discrete Math 330(6) (2014), 17–19), Wang proved thatχ s ′ ( G ) ≤ ( 4 k − 2 ) Δ − 2 k 2 + 1 . If G is a partial k ‐tree, in (M. Debski, J. Grytczuk, M. Sleszynska‐Nowak, Inf Process Lett 115(2) (2015), 326–330), it is proven thatχ s ′ ( G ) ≤ ( k + 1 ) ( Δ ( G ) + 1 ) . Let L ( G ) be the line graph of a graph G , and letL 2 ( G )be the square of the line graph L ( G ) . Thenχ s ′ ( G ) = χ ( L 2 ( G ) ) . We prove that if a graph G has an orientation with maximum out‐degree k , thenL 2 ( G )has coloring number at most 4 k Δ ( G ) − 2 k − 1 . If G is a k ‐tree, thenL 2 ( G )has coloring number at most( k + 1 ) Δ ( G ) − k ( k + 1 ) 2 . As a consequence, a graph withMad ( G ) ≤ 2 k hasχ s ′ ( G ) ≤ 4 k Δ ( G ) − 2 k − 1 , and a k ‐tree G hasχ s ′ ( G ) ≤ ( k + 1 ) Δ ( G ) − k ( k + 1 ) 2 .