A stronger bound for the strong chromatic index

2015/04/10 by Henning Bruhn, Felix Joos, Bruhn, Henning +1 · 3 citations
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR) #cs.DM #math.CO #math.PR

paper · pdf · doi:10.48550/arxiv.1504.02583

22 pages

arxiv created 2015/04/10 · arxiv updated 2015/04/13

Abstract

We prove χ_s'(G)≤ 1.93 Δ(G)² 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.

Cited by

• Toward Vu's conjecture
• Eigenvalue bounds for distance-edge colorings
• Strong edge-coloring of graphs with maximum edge weight seven

Related

• The Strong Chromatic Index of graphs with maximum degree Δ
• Strong chromatic index of chordless graphs
• Strong chromatic index of graphs with maximum degree four
• Strong chromatic index of bipartite graphs
• On the precise value of the strong chromatic-index of a planar graph with a large girth