← All problems

Balogh-Kostochka-Treglown degree-sequence conjecture for equitable colorings

Let n,k∈Nn,k∈\mathbb{N} with k≤nk≤n. Let GG be an nn-vertex graph whose degree sequence is d1≥⋯≥dnd_1≥⋯≥d_n. Let an equitable kk-coloring be a proper kk-coloring whose color classes have sizes differing by at most one. Degree-sequence equitable-coloring conjecture. If

di<2k−ifor all i<k,d_i<2k-i\quad\text{for all }i<k,

and

dk+1<k,d_{k+1}<k,

then GG contains an equitable kk-coloring.

This conjecture is proposed as a degree-sequence analogue of the Hajnal-Szemerédi conjecture, inspired by work of Balogh, Kostochka, and Treglown. Its general status is open.

References
  1. Yangyang Cheng, Zhenyu Li, Wanting Sun and Guanghui Wang, “A step toward Chen-Lih-Wu conjecture”, arXiv:2511.03957 (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.