← All problems

Grünbaum's equitable coloring conjecture

7 years old · traced to

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.

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.

Status

  • Solved: András Hajnal and Endre Szemerédi. Proof of a conjecture of P. Erdős (Combinatorial Theory and Its Applications, Vol. II (Proceedings of the Colloquium, Balatonfüred, 1969), 1970) https://arxiv.org/html/2504.14711

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

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.