In contrast to the $$(\varDelta +1)$$ -vertex coloring problem, the $$\varDelta $$ -vertex coloring problem cannot be solved with a simple sequential greedy algorithm. As a result it has become one of the prototypical problems for understanding the complexity of non-greedy distributed graph problems on constant-degree graphs. The major open problem is whether the problem can be solved deterministically in logarithmic time, which would match the lower bound [Chang et al., FOCS’16]. Despite recent progress in the design of efficient $$\varDelta $$ -coloring algorithms, we lack an asymptotically optimal algorithm. In this work we present a $$O(\log n)$$ -round deterministic $$\varDelta $$ -coloring algorithm for locally dense constant-degree graphs, matching the lower bound for the problem on general graphs. For general $$\varDelta $$ the algorithms’ complexity is $$\min \{\widetilde{O}(\log ^{5/3}n),O(\varDelta +\log n)\}$$ . Almost all recent distributed and sublinear graph coloring algorithms (also for coloring with more than $$\varDelta $$ colors) decompose the graph into sparse and dense parts. Our algorithm works for the case that this decomposition has no sparse vertices. Ironically, in recent (randomized) $$\varDelta $$ -coloring algorithms, dealing with sparse parts was relatively easy and these dense parts arguably posed the major hurdle. We present a solution that addresses the dense parts and may have the potential for extension to sparse parts. Our approach is fundamentally different from prior deterministic algorithms and hence hopefully contributes towards designing an optimal algorithm for the general case, and potentially also for other non-greedy problems. Additionally, we leverage our result to also obtain a randomized $$\min \{\widetilde{O}(\log ^{5/3}\log n), O(\varDelta +\log \log n)\}$$ -round algorithm for $$\varDelta $$ -coloring locally dense graphs that also matches the lower bound for the problem on general constant-degree graphs [Brandt et al.; STOC’16].

Publisher Copyright: © 2026 Copyright held by the owner/author(s).

The Δ-vertex coloring problem has become one of the prototypical problems for understanding the complexity of local distributed graph problems on constant-degree graphs. The major open problem is whether the problem can be solved deterministically in logarithmic time, which would match the lower bound [Chang et al., FOCS'16]. Despite recent progress in the design of efficient Δ-coloring algorithms, there is currently a polynomial gap between the upper and lower bounds.

There is a huge difference in techniques and runtimes of distributed algorithms for problems that can be solved by a sequential greedy algorithm and those that cannot. A prime example of this contrast appears in the edge coloring problem: while (2Δ-1)-edge coloring - where Δ is the maximum degree - can be solved in 𝒪(log^{∗}(n)) rounds on constant-degree graphs, the seemingly minor reduction to (2Δ-2) colors leads to an Ω(log n) lower bound [Chang, He, Li, Pettie & Uitto, SODA'18]. Understanding this sharp divide between very local problems and inherently more global ones remains a central open question in distributed computing and it is a core focus of this paper. As our main contribution we design a deterministic distributed 𝒪(log n)-round reduction from the (2Δ-2)-edge coloring problem to the much easier (2Δ-1)-edge coloring problem. This reduction is optimal, as the (2Δ-2)-edge coloring problem admits an Ω(log n) lower bound that even holds on the class of constant-degree graphs, whereas the 2Δ-1-edge coloring problem can be solved in 𝒪(log^{∗}n) rounds. By plugging in the (2Δ-1)-edge coloring algorithms from [Balliu, Brandt, Kuhn & Olivetti, PODC'22] running in 𝒪(log^{12}Δ + log^{∗} n) rounds, we obtain an optimal runtime of 𝒪(log n) rounds as long as Δ = 2^{𝒪(log^{1/12} n)}. Previously, such an optimal algorithm was only known for the class of constant-degree graphs [Brandt, Maus, Narayanan, Schager & Uitto, SODA'25]. Furthermore, on general graphs our reduction improves the runtime from 𝒪̃(log³ n) to 𝒪̃(log^{5/3} n). In addition, we also obtain an optimal 𝒪(log log n)-round randomized reduction of (2Δ - 2)-edge coloring to (2Δ - 1)-edge coloring. This leads to a 𝒪̃(log^{5/3} log n)-round (2Δ-2)-edge coloring algorithm, which beats the (very recent) previous state-of-the-art taking 𝒪̃(log^{8/3}log n) rounds from [Bourreau, Brandt & Nolin, STOC'25]. Lastly, we obtain an 𝒪(log_Δ n)-round reduction from the (2Δ-1)-edge coloring, albeit to the somewhat harder maximal independent set (MIS) problem.