Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition

We present a simple deterministic distributed algorithm that computes a (∆ + 1)-vertex coloring in O(log 2 ∆•log n) rounds. The algorithm can be implemented with O(log n)-bit messages. The algorithm can also be extended to the more general (degree + 1)-list coloring problem.

Obtaining a polylogarithmic-time deterministic algorithm for (∆ + 1)-vertex coloring had remained a central open question in the area of distributed graph algorithms since the 1980s, until a recent network decomposition algorithm of Rozhoň and Ghaffari [STOC'20]. The current state of the art is based on an improved variant of their decomposition, which leads to an O(log 5 n)-round algorithm for (∆ + 1)-vertex coloring.

Our coloring algorithm is completely different and considerably simpler and faster. It solves the coloring problem in a direct way, without using network decomposition, by gradually rounding a certain fractional color assignment until reaching an integral color assignments. Moreover, via the approach of Chang, Li, and Pettie [STOC'18], this improved deterministic algorithm also leads to an improvement in the complexity of randomized algorithms for (∆ + 1)-coloring, now reaching the bound of O(log 3 log n) rounds.

As a further application, we also provide faster deterministic distributed algorithms for the following variants of the vertex coloring problem. In graphs of arboricity a, we show that a (2 + ε)a-vertex coloring can be computed in O(log 3 a • log n) rounds. We also show that for ∆ ≥ 3, a ∆-coloring of a ∆-colorable graph G can be computed in O(log 2 ∆ • log 2 n) rounds.

Other implications, randomized coloring. By plugging our deterministic list-coloring algorithm into the randomized coloring algorithm of Chang et al. [CLP18], we can also improve the randomized complexity from the O(log 5 log n) bound of [GGR21] to O(log 3 log n):

Corollary 1.2. There is a randomized algorithm in the LOCAL model that computes a (∆ + 1)coloring in any graph with at most n nodes and maximum degree at most ∆ in O(log 3 log n) rounds, with high probability 1 .

We note that in a very recent paper, Halldórsson, Nolin, and Tonoyan [HNT21] give an improved randomized CONGEST algorithm for (∆ + 1)-coloring. Their algorithm can use the deterministic CONGEST algorithm that we give in Theorem 1.1 and by applying our result, they show that (∆ + 1)-coloring can also be solved in O(log 3 log n) rounds in the randomized CONGEST model.