Exact bounds for distributed graph colouring

Joel Rybicki and Jukka Suomela.

Christian Scheideler (Ed.): Proceedings of the 22nd International Colloquim on Structural Information and Communication Complexity (SIROCCO 2015), Montserrat, Spain, July 14-16, 2015.

Lecture Notes in Computer Science, 9439
Springer, Berlin Heidelberg, 2015
ISBN: 978-3-319-25258-2
pages 46-60



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{2}{2}\log^*(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^* n$ communication rounds.