Fast Distributed Brooks' Theorem
Manuela Fischer, Magnús M. Halldórsson, Yannic Maus · Society for Industrial and Applied Mathematics eBooks · 2023
We give a randomized Δ-coloring algorithm in the LOCAL model that runs in poly log log n rounds, where n is the number of nodes of the input graph and Δ is its maximum degree. This means that randomized Δ-coloring is a rare distributed coloring problem with an upper and lower bound in the same ballpark, poly log log n, given the known Ω(logΔ logn) lower bound [Brandt et al., STOC '16].