Exact bounds for distributed graph colouring

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 frac12 log^*(n) ± 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 frac12 log^* n communication rounds.