2015/02/17 by Joel Rybicki, Jukka Suomela, Rybicki, Joel +1 · 2 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Optimization and Search Problems #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1502.04963
openalex publication_date 2015/02/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 (1)/(2) 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 (1)/(2) log^* n communication rounds.