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 }^{\ast }n)$-round algorithm up to the ${\log }^{\ast }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 }^{\ast }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 }^{\ast }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.

54 pages, 5 figures, 1 table