Paperlane

no. 12 · Tuesday 10 November 2026

The Brualdi–Quinn conjecture on strong edge-coloring holds fractionally and asymptotically

Rong Luo, Gexin Yu and Xiangqian Zhou

math.CO · 8 pp

Abstract

Let $G$ be a bipartite graph with parts $A$ and $B$, and let $Δ_A$ and $Δ_B$ be the maximum degrees of the vertices in $A$ and in $B$, respectively. Brualdi and Quinn conjectured that the strong chromatic index of $G$ is at most $Δ_AΔ_B$. We prove that the fractional strong chromatic index of $G$ is at most $Δ_AΔ_B$, and that the conjecture holds asymptotically: $χ_s'(G)\le(1+o(1))Δ_AΔ_B$ as $\max\{Δ_A,Δ_B\}\to\infty$. The error term is $12(\lnΔ)^{1/2}Δ^{-1/4}$ with $Δ=\max\{Δ_A,Δ_B\}$. Both results rest on a smart partition of edges and Lovász Local Lemma.

comments
8 pages. Comments are welcome
fields
Combinatorics
pdf ↗ page arXiv:2611.10883 ↗