Equitable coloring of large bipartite graphs
This addresses a theoretical graph coloring problem for bipartite graphs, offering an optimal bound and efficient algorithm, but it is incremental as it builds on existing equitable coloring research.
The paper tackles the problem of equitable coloring in large bipartite graphs, proving that for graphs with sufficiently large maximum degree and size, the equitable chromatic number is at most ⌈Δ(G)/2⌉ + 1, which is optimal in terms of Δ(G), and provides an O(|V(G)|^2)-time algorithm for constructing such a coloring.
For a graph $G$, the \emph{equitable chromatic number} of $G$, denoted by $Ï_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 $ζ>41/2$, there exists a constant $c=c(ζ)\in\mathbb{N}$ such that every bipartite graph $G$ with maximum degree $Î(G)\ge c$ and $|V(G)|\ge ζÎ(G)$ satisfies $Ï_e(G)\le \left\lceilÎ(G)/2\right\rceil+1$. The leading term $Î(G)/2$ in this bound is best possible for upper bounds stated solely in terms of $Î(G)$ for bipartite graphs. Our proof yields an $O(|V(G)|^2)$-time algorithm for constructing such a coloring.