Search papers, labs, and topics across Lattice.
This paper presents a distributed LOCAL algorithm for vertex coloring that, given an integer $k<k_\Delta$ (where $k_\Delta$ is related to the maximum degree $\Delta$), computes a valid $\Delta-k$-coloring if one exists. The algorithm achieves a runtime of $\tilde{O}(\log^4 \log n)$ rounds, significantly improving upon existing algorithms, especially for small $\Delta$. This runtime approaches the known $\Omega(\log\log n)$ lower bound for distributed vertex coloring.
Distributed vertex coloring can now be solved in near-optimal $\tilde{O}(\log^4 \log n)$ rounds, closing the gap with the theoretical lower bound and exponentially improving performance for graphs with small maximum degree.
For any $\Delta$, let $k_\Delta$ be the maximum integer $k$ such that $(k+1)(k+2)\le \Delta$. We give a distributed \LOCAL algorithm that, given an integer $k<k_\Delta$, computes a valid $\Delta-k$-coloring if one exists. The algorithm runs in $\tilde{O}(\log^4 \log n)$ rounds, which is within a polynomial factor of the $\Omega(\log\log n)$ lower bound, which already applies to the case $k=0$. It is also best possible in the sense that if $k \ge k_\Delta$, the problem requires $\Omega(n/\Delta)$ distributed rounds [Molloy, Reed,'14, Bamas, Esperet'19]. For $\Delta$ at most polylogarithmic, the algorithm is an exponential improvement over the current state of the art of $O(\log^{49/12} n)$ rounds. When $\Delta \ge (\log n)^{50}$, our algorithm achieves an even faster runtime of $O(\log^* n)$ rounds.
