Parallel Batch Dynamic Vertex Coloring in O(log Δ) Amortized Update Time

2025/12/09 by Hutton, Chase, Melrod, Adam
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods #Parallel #and Cluster Computing (cs.DC)

paper · doi:10.48550/arxiv.2512.08742

openalex publication_date 2025/12/09 · openalex created_date 2025/12/11 · openalex updated_date 2026/07/28

Abstract

We present the first parallel batch-dynamic algorithm for maintaining a proper (Δ+ 1)-vertex coloring. Our approach builds on a new sequential dynamic algorithm inspired by the work of Bhattacharya et al. (SODA'18). The resulting randomized algorithm achieves O(log Δ) expected amortized update time and, for any batch of b updates, has parallel span O(polylog b + polylog n) with high probability.

Citations

• Parallel Batch-Dynamic Coreness Decomposition with Worst-Case Guarantees
• Parallel Batch-Dynamic Maximal Matching with Constant Work per Update
• Parallel Batch-Dynamic kd-Trees
• Parallel Batch-Dynamic Algorithms for k-Core Decomposition and Related Graph Problems
• A Parallel Batch-Dynamic Data Structure for the Closest Pair Problem
• Explicit and Implicit Dynamic Coloring of Graphs with Bounded Arboricity
• Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds
• Constant-Time Dynamic (Δ+1)-Coloring and Weight Approximation for Minimum Spanning Forest: Dynamic Algorithms Meet Property Testing
• Dynamic Algorithms for Graph Coloring

Related

• Dynamic Graph Coloring: Sequential, Parallel, and Distributed
• Fully Dynamic (Δ+1)-Coloring in Constant Update Time
• Faster Dynamic (Δ+1)-Coloring Against Adaptive Adversaries
• Dynamic Algorithms for Graph Coloring
• Dynamic O(arboricity) coloring in polylogarithmic worst-case time