Proper graph colorings with similar sized color classes

Question

In Grunbaum's paper, A result on graph coloring, the following conjecture was posed:

Let $G$ be a graph with $n$ nodes with $\Delta(G) < k$. There exists a proper $k$-coloring $c:V(G)\to [k]$ such that for each color $i\in [k]$, we have $\lfloor n/k\rfloor \le |c^{-1}(i)| \le \lfloor n/k\rfloor+1$.

The aforementioned paper demonstrated it was true for $k \le 4$, and mentions an upcoming paper proving $k = \lfloor k/3\rfloor,\lfloor k/2\rfloor$. I was wondering if this problem has received any further attention.

I feel that recently there has been a lot of results about applying Lovász Local Lemma to get specialized colorings of bounded degree graphs (such as frugal colorings and DP-colorings). I would assume that these methods would be well-suited to at least getting asymptotic results for the above conjecture. Has this been attempted/considered recently?

Answer 1

As mentioned in Grunbaum's paper, this is a conjecture of Erdős from 1964. It was solved completely by Hajnal and Szemerédi in 1970 and is now known as the Hajnal-Szemerédi theorem. A simpler proof was given by Kierstead and Kostochka in 2008. See the wikipedia page on equitable coloring for more information and links.