📖
Dynamic $(Δ+1)$-Coloring Against an Adaptive Adversary: Faster, Simpler, Worst-Case, and Bounded Recourse
Yuval Gil, Magnús M. Halldórsson

Dynamic $(Δ+1)$-Coloring Against an Adaptive Adversary: Faster, Simpler, Worst-Case, and Bounded Recourse

Author / Organization:
Science & Mathematics Published 2026 Verification Pending

Overview & Synopsis

We study fully dynamic $(Δ+1)$-coloring against an adaptive adversary. Behnezhad, Rajaraman, and Wasim (SODA 2025) gave the first algorithm with $\tilde O(n^{8/9})$ amortized update time, later improved to $\tilde O(n^{2/3})$ by Flin and Halldórsson (ICALP 2025). We give a fully dynamic $(Δ+1)$-coloring algorithm with $\tilde O(\sqrt n)$ \textbf{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 $3$.

Indexed from repository: arXiv (arxiv.org)
Loading document from verified source...
Keyboard Shortcuts: ← / → for pages • + / - for zoom • 0 to fit width Powered by Mozilla PDF.js v3.11

Document Information

Document Title Dynamic $(Δ+1)$-Coloring Against an Adaptive Adversary: Faster, Simpler, Worst-Case, and Bounded Recourse
Author / Organization Yuval Gil, Magnús M. Halldórsson
Subject & Discipline cs.DS
Categories Science & Mathematics
Publication Year 2026
License / Rights arXiv Open Access / Creative Commons
Resource Verification Listed PDF (Verification Pending)
Original Host Website arXiv (arxiv.org)
File Format application/pdf (Portable Document Format)
Language EN
Catalog ID DOC-273228
Original Source Link Visit Source Page on arxiv.org »