Erdős–Nešetřil conjecture on the strong chromatic index

Let GG be a finite simple graph with maximum degree Δ\Delta.

Erdős–Nešetřil conjecture. The strong chromatic index of GG satisfies

χs(G){54Δ2if Δ is even,54Δ212Δ+14if Δ is odd.\chi'_s(G)\le\begin{cases} \frac{5}{4}\Delta^2 &\text{if } \Delta \text{ is even}, \\ \frac{5}{4}\Delta^2-\frac{1}{2}\Delta+\frac{1}{4} &\text{if } \Delta \text{ is odd}. \end{cases}

The first non-trivial case, Δ=3\Delta=3, has been verified, but the conjecture remains open for Δ4\Delta\ge 4.

Sources & referencesView supporting material

Primary source

Runze Wang, “Proper edge coloring with rainbow diamonds”, arXiv:2606.06831 (2026).

Additional references

22 papers in this index state this conjecture (2012–2026). The statement above is taken from the most recent of them; the others are arXiv:2606.04856, arXiv:2603.15207, arXiv:2602.03862, arXiv:2509.06808, arXiv:2505.20345, arXiv:2301.12924, arXiv:2205.14680, arXiv:1810.06704, arXiv:1711.03464, arXiv:1508.03515, arXiv:1508.03052, arXiv:1507.08959, and 9 more.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.