Faster Dynamic $(\mathrm{\Delta }+1)$-Coloring Against Adaptive Adversaries

We consider the problem of maintaining a proper $(\mathrm{\Delta }+1)$-vertex coloring in a graph on $n$-vertices and maximum degree $\mathrm{\Delta }$ undergoing edge insertions and deletions. We give a randomized algorithm with amortized update time $\tilde{O}(n^{2\mathrm{/}3})$ against adaptive adversaries, meaning that updates may depend on past decisions by the algorithm. This improves on the very recent $\tilde{O}(n^{8\mathrm{/}9})$-update-time algorithm by Behnezhad, Rajaraman, and Wasim (SODA 2025) and matches a natural barrier for dynamic $(\mathrm{\Delta }+1)$-coloring algorithms. The main improvements are in the densest regions of the graph, where we use structural hints from the study of distributed graph algorithms.