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 constant-degree 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 (loglog 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 Ω(loglog 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.

Authors

• Yann Bourreau
• Sebastian Brandt 0002
• Alexandre Nolin

Keywords

• Brooks' theorem
• Distributed computing
• Graph coloring
• LOCAL model