A Stronger Bound for the Strong Chromatic Index

Source abstract

We prove χ′ s ( G ) ≤ 1.93 Δ( G ) 2 for graphs of sufficiently large maximum degree where χ′ s ( G ) is the strong chromatic index of G . This improves an old bound of Molloy and Reed. As a by-product, we present a Talagrand-type inequality where we are allowed to exclude unlikely bad outcomes that would otherwise render the inequality unusable.