Equitable coloring of large bipartite graphs

For a graph $G$, the \emph{equitable chromatic number} of $G$, denoted by ${\chi }_e(G)$, is the smallest integer $k$ such that $G$ admits a proper $k$-coloring whose color classes differ in size by at most one. We prove that for every $\zeta >41\mathrm{/}2$, there exists a constant $c=c(\zeta )\in \mathbb{N}$ such that every bipartite graph $G$ with maximum degree $\mathrm{\Delta }(G)\ge c$ and $\mathrm{\mid }V(G)\mathrm{\mid }\ge \zeta \mathrm{\Delta }(G)$ satisfies ${\chi }_e(G)\le \lceil \mathrm{\Delta }(G)\mathrm{/}2\rceil +1$. The leading term $\mathrm{\Delta }(G)\mathrm{/}2$ in this bound is best possible for upper bounds stated solely in terms of $\mathrm{\Delta }(G)$ for bipartite graphs. Our proof yields an $O(\mathrm{\mid }V(G){\mathrm{\mid }}^2)$-time algorithm for constructing such a coloring.