# Exact bounds for distributed graph colouring

SIROCCO 2015 · 22nd International Colloquium on Structural Information and Communication Complexity, Montserrat, Spain, July 2015 ·

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

# 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