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

Less than 1 year old · traced to

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):uv∈E(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)4⌉2−8⌈θ(G)4⌉+3if θ(G)≡1mod  4,5⌈θ(G)4⌉2−6⌈θ(G)4⌉+2if θ(G)≡2mod  4,5⌈θ(G)4⌉2−4⌈θ(G)4⌉+1if θ(G)≡3mod  4,5⌈θ(G)4⌉2if θ(G)≡0mod  4.\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.

References

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.