# Exact bounds for distributed graph colouring

arXiv: https://arxiv.org/abs/1502.04963 · HTML: https://mlsanity.com/paper/1502.04963/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Feb 2015.

## Built on by (most cited first, 1 of 1)

- [Learning Randomized Algorithms with Transformers](https://mlsanity.com/paper/2408.10818/) (2024)

## Abstract (arXiv)

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.