{"id":"arxiv/2604.05146","url":"https://arxiv.org/abs/2604.05146","tags":["math.CO","cs.DM"],"score":0,"title":"Equitable coloring of large bipartite graphs","domain":"math.CO","source":"arxiv","authors":["Amir Nikabadi"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-06","reactions":{}}