%0 Journal Article
%T Exact bounds for distributed graph colouring
%A Joel Rybicki
%A Jukka Suomela
%J Computer Science
%D 2015
%I arXiv
%X 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.
%U http://arxiv.org/abs/1502.04963v2