Faster Dynamic $(Δ+1)$-Coloring Against Adaptive Adversaries
Maxime Flin, Magnús M. Halldórsson · arXiv (Cornell University) · 2025
We consider the problem of maintaining a proper $(Δ+ 1)$-vertex coloring in a graph on $n$-vertices and maximum degree $Δ$ undergoing edge insertions and deletions. We give a randomized algorithm with amortized update time $\widetilde{O}( n^{2/3} )$ against adaptive adversaries, meaning that updates may depend on past decisions by the algorithm. This improves on the very recent $\widetilde{O}( n^{8/9} )$-update-time algorithm by Behnezhad, Rajaraman, and Wasim (SODA 2025) and matches a natural barrier for dynamic $(Δ+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.