# An Optimal Distributed (Delta+1)-Coloring Algorithm?

arXiv: https://arxiv.org/abs/1711.01361 · HTML: https://mlsanity.com/paper/1711.01361/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Nov 2017.

## Built on by (most cited first, 1 of 1)

- [Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions](https://mlsanity.com/paper/2109.14528/) (2021)

## Abstract (arXiv)

Vertex coloring is one of the classic symmetry breaking problems studied in distributed computing. In this paper we present a new algorithm for (Delta+1)-list coloring in the randomized sf LOCAL model running in O(mathsfDetscriptscriptstyle d(poly log n)) time, where mathsfDetscriptscriptstyle d(n') is the deterministic complexity of (deg+1)-list coloring on n'-vertex graphs. (In this problem, each v has a palette of size deg(v)+1.) This improves upon a previous randomized algorithm of Harris, Schneider, and Su [STOC'16, JACM'18] with complexity O(√log Delta + loglog n + mathsfDetscriptscriptstyle d(poly log n)), and, for some range of Delta, is much faster than the best known deterministic algorithm of Fraigniaud, Heinrich, and Kosowski [FOCS'16] and Barenboim, Elkin, and Goldenberg [PODC'18], with complexity O(√Deltalog Deltalog^ast Delta + log^* n). Our algorithm "appears to be" optimal, in view of the Omega(mathsfDet(poly log n)) randomized lower bound due to Chang, Kopelowitz, and Pettie [FOCS'16], where mathsfDet is the deterministic complexity of (Delta+1)-list coloring. At present, the best upper bounds on mathsfDetscriptscriptstyle d(n') and mathsfDet(n') are both 2^O(√log n') and use a black box application of network decompositions (Panconesi and Srinivasan [Journal of Algorithms'96]). It is quite possible that the true complexities of both problems are the same, asymptotically, which would imply the randomized optimality of our (Delta+1)-list coloring algorithm.