Dynamic -Coloring Against an Adaptive Adversary: Faster, Simpler, Worst-Case, and Bounded Recourse
In the authors' words
We study fully dynamic -coloring against an adaptive adversary. Behnezhad, Rajaraman, and Wasim (SODA 2025) gave the first algorithm with amortized update time, later improved to by Flin and Halld\'orsson (ICALP 2025). We give a fully dynamic -coloring algorithm with worst-case update time. Unlike previous algorithms, it avoids sparse-dense decompositions and relies only on elementary data structures, resulting in a short self-contained algorithm and analysis. Moreover, it avoids global recoloring, resulting in a worst-case recourse of .
Main resultThe abstract does not state a limitation.
Appeared: Tuesday, October 20. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: To appear in SODA 2027