Dynamic graph coloring made faster simpler and more stable
Dynamic $(Δ+1)$-Coloring Against an Adaptive Adversary: Faster, Simpler, Worst-Case, and Bounded Recourse
Data Structures and Algorithms
Summary
Coloring a graph means assigning colors to connected points so no neighbors share the same color. This paper improves how fast and smoothly we can update these colors when the graph changes, even if changes depend on previous colors. The authors designed a simpler, faster method that reacts quickly without needing complex steps or big reshuffles of colors. Their method limits the number of color changes needed after each update, ensuring stability and efficiency.
What this means in practice
- •For network schedulers: Update frequency assignments quickly under changing network conditions with minimal disruptions to existing allocations.
- •For real-time traffic controllers: Maintain efficient traffic light timings dynamically as traffic patterns change without costly global recalculations.
Authors
Yuval Gil, Magnús M. Halldórsson
Abstract
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$.