2026/08/03 by Amit Nir, David Peleg
Computer Science · #cs.DC #cs.DS
17 pages
arxiv created 2026/08/03 · arxiv updated 2026/08/05
This paper presents two randomized proper-coloring algorithms that control color frequencies in the synchronous CONGEST model without paying a diameter-dependent coordination cost. Let λ≥ 1 denote the desired failure exponent. For every fixed δ> 0, the first algorithm uses χ= \lceil (2+δ)Δ\rceil colors and, with probability at least 1 - n-λ, outputs a proper coloring that bounds the deviation of every color frequency from n/χ by Oδ(√((λ+1)(n/χ)\lg n) + (λ+1)\lg n). Under an explicit load condition, this additive guarantee yields two-sided relative balance. The second algorithm works with every χ> Δ and gives a one-sided frequency cap controlled by the palette slack χ- Δ. In particular, it uses Δ+ \lceil (Δ+1)/\lceil ln n \rceil \rceil colors and caps every used color class by O((λ+1)(σ\lg2 n + \lg n)), where σ= n/(Δ+1). Both algorithms run in O((λ+1)\lg n) rounds, with no dependence on the network diameter; for the first algorithm, the multiplicative constant in the time bound depends on δ.