Mahdian's conjecture for strong edge coloring of K_{t,t}-free graphs

At least 5 years old · documented by 2020

Let $t\geq 2$ be fixed, and let $G$ be a $K_{t,t}$ -free graph of maximum degree $d$ . Let $\chi'_s(G)$ denote its strong chromatic index. Mahdian's conjecture.

\chi'_s(G) \leq (2+o(1))\frac{d^2}{\log d}.

The paper proves a stronger result, namely an upper bound of $(1+\varepsilon)d^2/\log d$ for every fixed $\varepsilon>0$ and $t\geq2$ , when $d$ is sufficiently large; thus this conjecture is resolved.

References

Primary source

Richard Bi, Peter Bradshaw, Abhishek Dhawan and Jingwei Xu, “The strong chromatic index of K_t,t-free graphs”, arXiv:2603.15207 (2026).

Additional references

3 papers in this index state this conjecture (2020–2026). The statement above is taken from the most recent of them; the others are arXiv:2210.05915, arXiv:2003.10139.

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

A March 2026 preprint claims to have resolved the conjecture with an even stronger bound, but independent verification has not been found.

Mahdian conjectured in 2000 that every fixed $t\geq 2$ permits the asymptotic bound $\chi'_s(G)\leq (2+o(1))d^2/\log d$ for $K_{t,t}$ -free graphs of maximum degree $d$ .

Known results

Mahdian, 2000: the bound $\chi'_s(G)\leq (2+o(1))d^2/\log d$ for $C_4$ -free graphs.
Before the new preprint: $\chi'_s(G)\leq (2t-2+o(1))d^2/\log d$ for $K_{t,t}$ -free graphs.

16 March 2026 claimed resolution

Bi, Bradshaw, Dhawan, and Xu claim that, for every fixed $\varepsilon>0$ and $t\geq 2$ , sufficiently large $d$ gives $\chi'_s(G)\leq (1+\varepsilon)d^2/\log d$ , via a Rödl-nibble argument applied to $L(G)^2$ . This would resolve Mahdian’s conjecture, but the claim remains unverified.

Current status (as of September 2026): Mahdian’s conjecture is claimed resolved by the March 2026 preprint, with no independent verification or reported objection found in the retrieved sources.

Sources

No solutions have been posted yet.