In Grunbaum's paper, [A result on graph coloring](https://projecteuclid.org/journals/michigan-mathematical-journal/volume-15/issue-3/A-result-on-graph-coloring/10.1307/mmj/1029000043.full?tab=ArticleLinkCited), 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?



Proper graph colorings with similar sized color classes
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](https://en.wikipedia.org/wiki/Equitable_coloring) for more information and links.


