A stronger bound for the strong chromatic index

Abstract

We prove ${\chi }_s^{\prime }(G)\le 1.93\Delta (G{)}^2$ for graphs of sufficiently large maximum degree where ${\chi }_s^{\prime }(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.

22 pages