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² 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² 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.
ACM Symposium on Theory of Computing (STOC)
2025-06-23
2025-02-26