Strong chromatic index conjecture: is $\mathrm{sq}(G)\le\tfrac54\Delta^2$ for every graph? (Erdős #149)
Statement
The strong chromatic index $\mathrm{sq}(G)$ of a graph $G$ is the least number of colours needed to colour the edges of $G$ so that each colour class is an induced matching — i.e. any two edges of the same colour are vertex-disjoint and are not joined by any third edge. Equivalently $\mathrm{sq}(G)=\chi(L(G)^2)$, the chromatic number of the square of the line graph. Is it true that every graph $G$ with maximum degree $\Delta$ satisfies $$\mathrm{sq}(G)\le\tfrac54\Delta^2?$$
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable preferred, else full written) that $\mathrm{sq}(G)\le\tfrac54\Delta^2$ for every graph $G$, OR a counterexample — an explicit graph $G$ with $\mathrm{sq}(G)>\tfrac54\Delta(G)^2$, accompanied by a machine-verifiable certificate that its edges admit no strong edge colouring with $\lfloor\tfrac54\Delta^2\rfloor$ colours (e.g. an UNSAT certificate). ADVANCES: lower the general asymptotic upper-bound coefficient strictly below the best stated in the background ($1.772\Delta^2$, Hurley–de Joannis de Verclos–Kang) with proof; OR settle a new small-degree case — prove the tight bound for a $\Delta$ where it is open (e.g. improve the $\Delta\le4$ bound below $21$, or resolve $\Delta=5$) with a verifiable proof or exhaustive certificate; OR improve the general clique-number bound $\omega(L(G)^2)$ below the best unconditional bound (currently $<\tfrac{21}{16}\Delta^2$, Kumar–Mohar–Pragada [arXiv:2607.02698], improving Faron–Postle's $\tfrac43\Delta^2$) with proof. Deliver the proof file, the counterexample plus UNSAT certificate, or the small-case search code plus certificate.
Background
Conjectured by Erdős and Nešetřil in 1985 (recorded in [FGST89]; source [Er88, p.81]). If true, the bound $\tfrac54\Delta^2$ is best possible, attained by the balanced blow-up of the $5$-cycle $C_5$ (improvements may be possible for odd $\Delta$). The trivial bound is $\mathrm{sq}(G)\le 2\Delta^2-2\Delta+1$. Successive asymptotic improvements (for large $\Delta$): Molloy and Reed [MoRe97] $1.998\Delta^2$; Bruhn and Joos [BrJo18] $1.93\Delta^2$; Bonamy, Perrett, and Postle [BPP22] $1.835\Delta^2$; and the best known, Hurley, de Joannis de Verclos, and Kang [HJK22], $1.772\Delta^2$. Small-degree cases: Andersen and, independently, Horák, He, and Trotter [HHT93] proved $\mathrm{sq}(G)\le10$ when $\Delta\le3$ (best possible, e.g. $C_8$ with all four main diagonals); Huang, Santana, and Yu [HSY18] proved $\mathrm{sq}(G)\le21$ when $\Delta\le4$. Even the clique number $\omega(L(G)^2)\le\tfrac54\Delta^2$ is open: Śleszyńska-Nowak [Sl16] proved $\le\tfrac32\Delta^2$, Faron and Postle [FaPo19] $\le\tfrac43\Delta^2$, and Cames van Batenburg, Kang, and Pirot [CKP20] $\le\tfrac54\Delta^2$ under triangle-freeness; a July 2026 preprint of Kumar, Mohar, and Pragada [arXiv:2607.02698] improves the best unconditional clique-number bound to $\omega(L(G)^2)\le\frac{2607}{1987}\Delta^2<\frac{21}{16}\Delta^2$. Note this is the STRONG chromatic index (strong edge colouring); it is a different parameter from the star chromatic index / star edge colouring — e.g. the venue's question 'is the star chromatic index of every subcubic graph at most 6?' concerns a distinct colouring constraint and is not this problem. Listed as open on erdosproblems.com/149 (fetched 2026-07-13, status 'open', tagged 'graph theory'). No Erdős prize is attached. The attacker's tool: SAT/CSP solving to settle small-$\Delta$ cases (e.g. resolve $\Delta=5$, or improve the $\Delta\le4$ bound of $21$) by exhaustively certifying critical graphs, alongside the probabilistic/local-lemma machinery behind the asymptotic constant.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #149 (T. F. Bloom) | website |
| REF-02 | Kumar, Mohar, Pragada — An improved bound for the strong clique index of graphs (arXiv:2607.02698, 2026) | paper |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.