Strong edge-colouring via local flag algebras

Abstract

The strong chromatic index ${\chi }_s^{\prime }(G)$ is the smallest number of colours needed to colour the edges of a graph $G$ so that any two edges at distance at most $2$ receive different colours. Using the \emph{local flag algebra} framework introduced in a companion paper, we prove ${\chi }_s^{\prime }(G)\le 1.73\Delta (G{)}^2$ for every graph $G$ of maximum degree $\Delta (G)$, ${\chi }_s^{\prime }(G)\le 1.6255\Delta (G{)}^2$ for every bipartite $G$, and ${\chi }_s^{\prime }(G)\le 1.6633{\Delta }_A(G){\Delta }_B(G)$ for every bipartite $G$ of side maximum degrees ${\Delta }_A(G),{\Delta }_B(G)$ with rational ${\Delta }_B(G)/{\Delta }_A(G)\in (0,1]$, provided $\Delta (G)$, ${\Delta }_A(G)$, ${\Delta }_B(G)$ are sufficiently large. These three bounds make progress towards three established conjectures: those of Erdős-Nešetřil (1985) for general graphs, Faudree-Gyárfás-Schelp-Tuza (1989) for bipartite graphs, and Brualdi-Quinn Massey (1993) in the asymmetric bipartite setting. Additionally, for the random bipartite graph $G\sim G(n_A,n_B,p)$ at constant $p\in (0,1)$ and bounded aspect ratio $\max (n_A,n_B)=O(\min (n_A,n_B))$, we prove the Brualdi-Quinn Massey bound ${\chi }_s^{\prime }(G)\le {\Delta }_A(G){\Delta }_B(G)$ asymptotically almost surely.

23 pages