Grünbaum's equitable coloring conjecture

Let GG be a graph with maximum degree Δ(G)\Delta(G), and let a kk-equitable coloring be a proper coloring with kk color classes whose sizes differ by at most one. Grünbaum's conjecture. Every graph GG with

Δ(G)<k\Delta(G)<k

has a kk-equitable coloring. The conjecture was proved by Hajnal and Szemerédi in 1970.

Sources & referencesView supporting material

Primary source

H. A. Kierstead, Alexandr Kostochka and Zimu Xiang, “Results and Problems on Equitable Coloring of Graphs”, arXiv:2504.14711 (2025).

Additional references

2 papers in this index state this conjecture (2019–2025). The statement above is taken from the most recent of them; the others are arXiv:1901.08622.

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.