Joel Rybicki · Jukka Suomela

Exact bounds for distributed graph colouring

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

authors’ version publisher’s version


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


This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.