






















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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。