Strong edge-colouring via local flag algebras

Abstract

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 \emph{local flag algebra} framework introduced in a companion paper, we prove $χ'_s(G) \leq 1.73\,Δ(G)^2$ for every graph $G$ of maximum degree $Δ(G)$, $χ'_s(G) \leq 1.6255\,Δ(G)^2$ for every bipartite $G$, and $χ'_s(G) \leq 1.6633\,Δ_A(G)\,Δ_B(G)$ for every bipartite $G$ of side maximum degrees $Δ_A(G), Δ_B(G)$ with rational $Δ_B(G)/Δ_A(G) \in (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 \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 $χ'_s(G) \leq Δ_A(G)\,Δ_B(G)$ asymptotically almost surely.

Disclosure

“coding effort used AI assistance. These results were made publicly accessible in 2024 via Eoin Davey’s MSc thesis [6] at the University of Amsterdam theses repository. During the third phase, we used one commercially available agentic AI system for the following purposes: 1. formal verification of the mathematical results in Lean 4; 2. empirical checks to sweep for potential counterexample graphs; 3. proof of subsidiary results (Theorem 1.4 and Proposition 8.1) under our”

PDF page 22

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T18:59:37.023403Z

Structural counts