Chen–Lih–Wu conjecture on the equitable chromatic threshold

Let GG be a connected graph, and let χ(G)\chi_{\equiv}(G) denote its equitable chromatic threshold and Δ(G)\Delta(G) its maximum degree.

Chen–Lih–Wu conjecture.

χ(G)Δ(G),\chi_{\equiv}(G)\leq \Delta(G),

with the exception that GG is a complete graph, an odd cycle, or a complete bipartite graph K2m+1,2m+1K_{2m+1,2m+1}.

The supplied source does not state whether this conjecture has been resolved, so it is recorded as open.

Sources & referencesView supporting material

Primary source

Yuping Gao, Allan Lo and Songling Shan, “Equitable tree colouring of graphs”, arXiv:2604.13606 (2026).

Additional references

15 papers in this index state this conjecture (2012–2026). The statement above is taken from the most recent of them; the others are arXiv:2604.05146, arXiv:2511.03957, arXiv:2504.14711, arXiv:2503.00222, arXiv:2411.19801, arXiv:2305.14056, arXiv:1803.07450, arXiv:1611.06031, arXiv:1601.03791, arXiv:1508.04201, arXiv:1506.03913, arXiv:1408.6046, and 2 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.