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].