2026/07/19 by Eoin Davey, Eoin Hurley, Rémi de Joannis de Verclos +2
#math.CO #cs.DM
The strong chromatic index χ's(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 local flag algebra framework introduced in a companion paper, we prove χ's(G) ≤ 1.73 Δ(G)2 for every graph G of maximum degree Δ(G), χ's(G) ≤ 1.6255 Δ(G)2 for every bipartite G, and χ's(G) ≤ 1.6633 ΔA(G) ΔB(G) for every bipartite G of side maximum degrees ΔA(G), ΔB(G) with rational ΔB(G)/ΔA(G) ∈ (0, 1], provided Δ(G), ΔA(G), Δ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 ∼ G(nA, nB, p) at constant p ∈ (0,1) and bounded aspect ratio max(nA, nB) = O(min(nA, nB)), we prove the Brualdi-Quinn Massey bound χ's(G) ≤ ΔA(G) ΔB(G) asymptotically almost surely.