Faster Distributed \(\Delta\)-Coloring via a Reduction to MIS
Yann Bourreau, Sebastian Brandt, Alexandre Nolin · Society for Industrial and Applied Mathematics eBooks · 2026
Recent improvements on the deterministic complexities of fundamental graph problems in the LOCAL model of distributed computing have yielded state-of-the-art upper bounds of \(\tilde{O}(\log^{5/3} n)\) rounds for maximal independent set (MIS) and \((\Delta + 1)\)-coloring [Ghaffari, Grunau, FOCS’24], and \(\tilde{O}(\log^{19/9} n)\) rounds for the more restrictive \(\Delta\)-coloring problem [Ghaffari, Kuhn, FOCS’21; Ghaffari, Grunau, FOCS’24; Bourreau, Brandt, Nolin, STOC’25]. In our work, we show that \(\Delta\)-coloring can be solved deterministically in \(\tilde{O}(\log^{5/3} n)\) rounds as well, matching the currently best bound for \((\Delta + 1)\)-coloring.