Diameter-Free Distributed Frequency Control for Graph Coloring in the CONGEST Model

Abstract

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 $\lambda \geq 1$ denote the desired failure exponent. For every fixed $\delta > 0$, the first algorithm uses $\chi = \lceil (2+\delta)\Delta \rceil$ colors and, with probability at least $1 - n^{-\lambda}$, outputs a proper coloring that bounds the deviation of every color frequency from $n/\chi$ by $O_\delta(\sqrt{(\lambda+1)(n/\chi)\lg n} + (\lambda+1)\lg n)$. Under an explicit load condition, this additive guarantee yields two-sided relative balance. The second algorithm works with every $\chi > \Delta$ and gives a one-sided frequency cap controlled by the palette slack $\chi - \Delta$. In particular, it uses $\Delta + \lceil (\Delta+1)/\lceil \ln n \rceil \rceil$ colors and caps every used color class by $O((\lambda+1)(\sigma \lg^2 n + \lg n))$, where $\sigma = n/(\Delta+1)$. Both algorithms run in $O((\lambda+1)\lg n)$ rounds, with no dependence on the network diameter; for the first algorithm, the multiplicative constant in the time bound depends on $\delta$.