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.

Publication

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

Links

• presentation, 15 July 2015