Sublogarithmic Distributed Vertex Coloring with Optimal Number of Colors

Abstract

For any $\hat{I}”$, let $k_{\hat{I}}”$ be the maximum integer $k$ such that $(k+1)(k+2)\le \hat{I}”$. We give a distributed \LOCAL algorithm that, given an integer $k<k_{\hat{I}}”$, computes a valid $\hat{I}”-k$-coloring if one exists. The algorithm runs in $\tilde{O}({\log }^4\log n)$ rounds, which is within a polynomial factor of the $\hat{I}\text{c◯}(\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_{\hat{I}}”$, the problem requires $\hat{I}\text{c◯}(n/\hat{I}”)$ distributed rounds [Molloy, Reed, '14, Bamas, Esperet '19]. For $\hat{I}”$ at most polylogarithmic, the algorithm is an exponential improvement over the current state of the art of $O({\log }^{49/12}n)$ rounds. When $\hat{I}”\ge (\log n{)}^{50}$, our algorithm achieves an even faster runtime of $O({\log }^{\ast }n)$ rounds.

To appear in STOC 2026