pipette
ESEspañol

Dynamic -Coloring Against an Adaptive Adversary: Faster, Simpler, Worst-Case, and Bounded Recourse

Yuval Gil, Magn\'us M. Halld\'orsson

Preprint

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