A Stronger Bound for the Strong Chromatic Index

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...

Full description

Saved in:
Bibliographic Details
Published in:Combinatorics, probability & computing probability & computing, 2018-01, Vol.27 (1), p.21-43
Main Authors: BRUHN, HENNING, JOOS, FELIX
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0963-5483
1469-2163
DOI:10.1017/S0963548317000244