Faster Distributed Δ-Coloring via Ruling Subgraphs

Brooks' theorem states that all connected graphs but odd cycles and cliques can be colored with ∆ colors, where ∆ is the maximum degree of the graph. Such colorings have been shown to admit non-trivial distributed algorithms [Panconesi and Srinivasan, Combinatorica 1995] and have been studied intensively in the distributed literature. In particular, it is known that any deterministic algorithm computing a ∆-coloring requires Ω(log n) rounds in the LOCAL model [Chang, Kopelowitz, and Pettie, FOCS 2016], and that this lower bound holds already on constantdegree graphs. In contrast, the best upper bound in this setting is given by an O(log 2 n)-round deterministic algorithm that can be inferred already from the works of [Awerbuch, Goldberg, Luby, and Plotkin, FOCS 1989] and [Panconesi and Srinivasan, Combinatorica 1995] roughly three decades ago, raising the fundamental question about the true complexity of ∆-coloring in the constant-degree setting.

We answer this long-standing question almost completely by providing an almost-optimal deterministic O(log n log * n)-round algorithm for ∆-coloring, matching the lower bound up to a log * n-factor. Similarly, in the randomized LOCAL model, we provide an O(log log n log * n)-round algorithm, improving over the state-of-the-art upper bound of O(log 2 log n) [Ghaffari, Hirvonen, Kuhn, and Maus, Distributed Computing 2021] and almost matching the Ω(log log n)-round lower bound by [BFHKLRSU, STOC 2016].

Our results make progress on several important open problems and conjectures. One key ingredient for obtaining our results is the introduction of ruling subgraph families as a novel tool for breaking symmetry between substructures of a graph, which we expect to be of independent interest.