Dynamic O(Arboricity) Coloring in Polylogarithmic Worst-Case Time

A recent work by Christiansen, Nowicki, and Rotenberg [STOC’23] provides dynamic algorithms for coloring sparse graphs, concretely as a function of the graph’s arboricity α. They give two randomized algorithms: O (α logα) implicit coloring in poly (log n ) worst-case update and query times, and O (min{α logα, α logloglog n }) implicit coloring in poly (log n ) amortized update and query times (against an oblivious adversary). We improve these results in terms of the number of colors and the time guarantee: First, we present an extremely simple algorithm that computes an O (α)-implicit coloring with poly (log n ) amortized update and query times. Second, and as the main technical contribution of our work, we show that the time complexity guarantee can be strengthened from amortized to worst-case. That is, we give a dynamic algorithm for implicit O (α)-coloring with poly (log n ) worst-case update and query times (against an oblivious adversary).

Authors

• Mohsen Ghaffari 0001
• Christoph Grunau

Keywords

• Coloring
• Dynamic Algorithms