Distributed Near-Equitable Coloring in the LOCAL Model

Abstract

For an $n$-vertex graph of maximum degree $\Delta$, an equitable $(\Delta+1)$-coloring is a proper coloring all of whose color classes have size $\sigma = n/(\Delta+1)$ up to rounding. Known algorithms for relaxations of this target aggregate along a spanning structure, at cost scaling with the diameter $D$. We study near-equitable coloring in the LOCAL model and prove that, for deterministic algorithms, exact balance is inherently global: already on the cycle $C_n$, exact balanced free $3$-coloring requires $\Omega(n)$ rounds. More generally, additive imbalance $g$ requires $\Omega(n/g)$ rounds, matching a deterministic $O((n/g)\log^* n)$-round algorithm up to the $\log^* n$ factor, and these problems realize a dense family of intermediate deterministic LOCAL complexities $\tilde\Theta(n^\alpha)$, $\alpha \in (0,1)$, on cycles. The exact bound is sharp in two further senses: the identifier-universe threshold is exactly $N=n+1$, and the $\log^* n$ gap cannot be closed via faster ruling-set anchors. The bound then extends to twisted fiber products, an explicit family realizing, for every $\Delta \ge 3$, every diameter scale from the Moore bound $\Theta(\log n/\log\Delta)$ up to $\Theta(n/\Delta)$. Exact equitable $(\Delta+1)$-coloring requires $\Theta(D)$ rounds deterministically on this family, so exactness costs diameter time already on bounded-degree graphs of logarithmic diameter. In contrast, coarse balance admits local algorithms. On cycles, constant multiplicative equity costs $\Theta(\log^* n)$ rounds. On general graphs with large color classes, all class sizes can be kept within $(1\pm\eta)$ times the average in time independent of the diameter: with palette exactly $\Delta+1$ for $\Delta \le 2^{\sqrt{\log n}/C}$, and with palette $(1+\eta)(\Delta+1)$ for every $\Delta \le n^{1-o(1)}$, the latter in $O(\log n\,(\log\log n)^2)$ rounds.