SIROCCO 2015 · 22nd International Colloquium on Structural Information and Communication Complexity, Montserrat, Spain, July 2015 · doi:10.1007/978-3-319-25258-2_4

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^*(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.

Christian Scheideler (Ed.): *Structural Information and Communication Complexity, 22nd International Colloquium, SIROCCO 2015, Montserrat, Spain, July 14–16, 2015, Post-Proceedings*, volume 9439 of *Lecture Notes in Computer Science*, pages 46–60, Springer, Berlin, 2015

ISBN 978-3-319-25257-5