Exact bounds for distributed graph colouring

Abstract

We prove exact bounds on the time complexity of distributed graph colouring. If we are given a directed path that is properly coloured with $n$ colours, by prior work it is known that we can find a proper 3-colouring in $\frac{1}{2}{\log }^{\ast }(n)\pm O(1)$ communication rounds. We close the gap between upper and lower bounds: we show that for infinitely many $n$ the time complexity is precisely $\frac{1}{2}{\log }^{\ast }n$ communication rounds.

16 pages, 3 figures