Equitable coloring of large bipartite graphs

Abstract

For a graph $G$, the \emph{equitable chromatic number} of $G$, denoted by $\ddot{I}{‡}_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 $\hat{I}\P >41/2$, there exists a constant $c=c(\hat{I}\P )\in \mathbb{N}$ such that every bipartite graph $G$ with maximum degree $\hat{I}”(G)\ge c$ and $|V(G)|\ge \hat{I}\P \hat{I}”(G)$ satisfies $\ddot{I}{‡}_e(G)\le \lceil \hat{I}”(G)/2\rceil +1$. The leading term $\hat{I}”(G)/2$ in this bound is best possible for upper bounds stated solely in terms of $\hat{I}”(G)$ for bipartite graphs. Our proof yields an $O(|V(G){|}^2)$-time algorithm for constructing such a coloring.