{"id":"arxiv/2609.25041","url":"https://arxiv.org/abs/2609.25041","tags":["math.CO"],"score":0,"title":"A square-root law for equitable coloring","domain":"math.CO","source":"arxiv","authors":["Mohammad F. Marashdeh"],"reviews":0,"subject":"math.CO","summary":"An equitable $k$-coloring of a graph partitions its vertex set into $k$ independent sets whose sizes differ by at most one; the least such $k$ is the equitable chromatic number $\\chie(G)$. Every known bound on $\\chie$ valid for all graphs, beginning with the Hajnal--Szemerédi theorem, is linear in the maximum degree $Δ$, and the star $K_{1,Δ}$, for which $\\chie=\\ceil{Δ/2}+1$, shows that no general bound below $Δ/2$ exists. We prove that this obstruction is a shortage of vertices rather than an effect of the degree: every graph with $|V(G)|\\ge3χ(G)Δ$ satisfies…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-28","reactions":{}}