2015/04/10 by Bruhn, Henning, Joos, Felix · 2 citations
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.1504.02583
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 it is allowed to exclude unlikely bad outcomes that would otherwise render the inequality unusable.