A square-root law for equitable coloring
Abstract
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 K1,Δ, 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)|≥3χ(G)Δ satisfies chie(G)=O(χ(G)3/2√(Δ/lnΔ)) throughout the range χ(G)≤(Δ/lnΔ)1/3, so that for graphs of large order the degree enters only through √(Δ/lnΔ), with the chromatic number governing the rest. For each fixed ℓ, ℓ-colorable graphs of sufficiently large order satisfy chie≤(2√2 ℓ√(ℓ−1)+o(1))√(Δ/lnΔ), while a probabilistic construction supplies graphs of arbitrarily large order, bipartite when ℓ=2, with chie≥1/3√((ℓ−1)Δ/lnΔ): the order of growth Θ(√(Δ/lnΔ)) is exact for every fixed chromatic number, and the extremal constant is determined up to a factor O(χ(G)). All upper bounds are constructive, and a prescribed-anchor variant of the construction produces equitable colorings of bipartite graphs with O(√Δ) colors in optimal linear time.
Related
- Order 14 is the largest order for which every 4-total coloring of every cubic graph is equitable
- Hitting Arithmetic Progressions at the Square-Root Scale
- MDS Algebraic Geometry Codes of Square-Root Length on Hyperelliptic Curves
- Component-wise accurate fixed point iterations for computing the square root of a singular M-matrix
- Square root cancellation in the hyperbolic lattice counting problem over cocompact groups
BibTeX
@misc{marashdeh2026squareroot,
title = {{A square-root law for equitable coloring}},
author = {Mohammad F. Marashdeh},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.25041},
eprint = {2609.25041},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.25041},
}
RIS
TY - UNPB
TI - A square-root law for equitable coloring
AU - Mohammad F. Marashdeh
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.25041
UR - https://arxiv.org/abs/2609.25041
AB - 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)|≥3χ(G)Δ satisfies chie(G)=O(χ(G)^3/2√(Δ/lnΔ)) throughout the range χ(G)≤(Δ/lnΔ)^1/3, so that for graphs of large order the degree enters only through √(Δ/lnΔ), with the chromatic number governing the rest. For each fixed ℓ, ℓ-colorable graphs of sufficiently large order satisfy chie≤(2√2 ℓ√(ℓ−1)+o(1))√(Δ/lnΔ), while a probabilistic construction supplies graphs of arbitrarily large order, bipartite when ℓ=2, with chie≥1/3√((ℓ−1)Δ/lnΔ): the order of growth Θ(√(Δ/lnΔ)) is exact for every fixed chromatic number, and the extremal constant is determined up to a factor O(χ(G)). All upper bounds are constructive, and a prescribed-anchor variant of the construction produces equitable colorings of bipartite graphs with O(√Δ) colors in optimal linear time.
ER -