Chen et al.'s Ore-degree conjecture for the strong chromatic index

Let GG be a finite simple connected graph. The Ore-degree of GG, denoted by θ(G)\theta(G), is

θ(G)=max{d(u)+d(v):uvE(G)}.\theta(G)=\max\{d(u)+d(v):uv\in E(G)\}.

Its strong chromatic index χs(G)\chi_s'(G) is the minimum number of colors in a strong edge-coloring, meaning that edges at distance at most 22 in the line graph receive distinct colors.

Chen et al.'s conjecture. If θ(G)5\theta(G)\ge 5, then

χs(G){5θ(G)428θ(G)4+3if θ(G)1mod4,5θ(G)426θ(G)4+2if θ(G)2mod4,5θ(G)424θ(G)4+1if θ(G)3mod4,5θ(G)42if θ(G)0mod4.\chi_s'(G)\le\begin{cases} 5\bigl\lceil\frac{\theta(G)}{4}\bigr\rceil^2-8\bigl\lceil\frac{\theta(G)}{4}\bigr\rceil+3 &\text{if } \theta(G)\equiv 1\mod 4,\\ 5\bigl\lceil\frac{\theta(G)}{4}\bigr\rceil^2-6\bigl\lceil\frac{\theta(G)}{4}\bigr\rceil+2 &\text{if } \theta(G)\equiv 2\mod 4,\\ 5\bigl\lceil\frac{\theta(G)}{4}\bigr\rceil^2-4\bigl\lceil\frac{\theta(G)}{4}\bigr\rceil+1 &\text{if } \theta(G)\equiv 3\mod 4,\\ 5\bigl\lceil\frac{\theta(G)}{4}\bigr\rceil^2 &\text{if } \theta(G)\equiv 0\mod 4.\end{cases}

This conjecture adapts the Erdős–Nešetřil bound by replacing maximum degree with Ore-degree. The case θ(G)=5\theta(G)=5 was verified by Wu and Lin, but the parser marks the conjecture as resolved without supplying evidence that the full statement has been proved; its database status is therefore recorded as open pending verification.

Sources & referencesView supporting material

Primary source

Runze Wang, “Strong edge-coloring of sparse graphs with Ore-degree 7 or 8”, arXiv:2602.03862 (2026).

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.