{"ID":2831258,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.08742","arxiv_id":"2512.08742","title":"Parallel Batch Dynamic Vertex Coloring in $O(\\log Δ)$ Amortized Update Time","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(\\operatorname{polylog} b + \\operatorname{polylog} n)$ with high probability.","short_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 ba...","url_abs":"https://arxiv.org/abs/2512.08742","url_pdf":"https://arxiv.org/pdf/2512.08742v1","authors":"[\"Chase Hutton\",\"Adam Melrod\"]","published":"2025-12-09T15:51:11Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.DC\"]","methods":"[]","has_code":false}