Faster Dynamic (Δ+1)-Coloring Against Adaptive Adversaries

2025/04/28 by Flin, Maxime, Halldórsson, Magnús M.
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2504.19729

Abstract

We consider the problem of maintaining a proper (Δ+ 1)-vertex coloring in a graph on n-vertices and maximum degree Δ undergoing edge insertions and deletions. We give a randomized algorithm with amortized update time \widetildeO( n^2/3 ) against adaptive adversaries, meaning that updates may depend on past decisions by the algorithm. This improves on the very recent \widetildeO( n^8/9 )-update-time algorithm by Behnezhad, Rajaraman, and Wasim (SODA 2025) and matches a natural barrier for dynamic (Δ+1)-coloring algorithms. The main improvements are in the densest regions of the graph, where we use structural hints from the study of distributed graph algorithms.

Citations

• Simple Sublinear Algorithms for (Δ+1) Vertex Coloring via Asymmetric Palette Sparsification
• Round and Communication Efficient Graph Coloring
• (Δ+ 1) Vertex Coloring in O(n) Communication
• Coloring Fast with Broadcasts
• A Distributed Palette Sparsification Theorem
• Ultrafast Distributed Coloring of High Degree Graphs
• The Multiplicative Version of Azuma's Inequality, with an Application to Contention Analysis
• Efficient Randomized Distributed Coloring in CONGEST
• Distributed (Δ +1)-Coloring in Sublogarithmic Rounds
• Dynamic Algorithms for Graph Coloring
• The Locality of Distributed Symmetry Breaking
• The Locality of Distributed Symmetry Breaking
• Locality in Distributed Graph Algorithms
• Fully Dynamic (Δ+1) Coloring Against Adaptive Adversaries

Related

• Fully Dynamic (Δ+1) Coloring Against Adaptive Adversaries
• Dynamic Algorithms for Graph Coloring
• Dynamic Graph Coloring: Sequential, Parallel, and Distributed
• Fully Dynamic (Δ+1)-Coloring in Constant Update Time
• Dynamic Graph Coloring