The Δ-Equitable Coloring Conjecture for connected graphs

Let $G$) be a connected graph, and let $\Delta(G)$ denote its maximum vertex degree. An equitable $k$-coloring is a proper coloring whose color classes differ in size by at most $1$; write $K_m$ for the complete graph, $C_{2m+1}$ for the odd cycle, and $K_{2m+1,2m+1}$ for the balanced complete bipartite graph. Δ-Equitable Coloring Conjecture. A connected graph $G$ is equitably $\Delta(G)$-colorable if it is different from $K_m$, $C_{2m+1}$, and $K_{2m+1,2m+1}$. This improves the Hajnál–Szemerédi bound by one for most connected graphs. It remains open, although it is known for interval, bipartite, outerplanar, subcubic, certain planar, and several other classes of graphs.