{"ID":2830499,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.09218","arxiv_id":"2512.09218","title":"Dynamic Graph Coloring: Sequential, Parallel, and Distributed","abstract":"We present a simple randomized algorithm that can efficiently maintain a $(Δ+1)$ coloring as the graph undergoes edge insertion and deletion updates, where $Δ$ denotes an upper bound on the maximum degree. A key advantage is the algorithm's ability to process many updates simultaneously, which makes it naturally adaptable to the parallel and distributed models. Concretely, it gives a unified framework across the models, leading to the following results: - In the sequential setting, the algorithm processes each update in $O(1)$ expected time, worst-case. This matches and strengthens the results of Henzinger and Peng [TALG 2022] and Bhattacharya et al. [TALG 2022], who achieved an $O(1)$ bound but amortized (in expectation and with high probability, respectively), whose work was an improvement of the $O(\\log Δ)$ expected amortized bound of Bhattacharya et al. [SODA'18]. - In the parallel setting, the algorithm processes each (arbitrary size) batch of updates using $O(1)$ work per update in the batch in expectation, and in $\\text{poly}(\\log n)$ depth with high probability. This is, in a sense, an ideal parallelization of the above results. - In the distributed setting, the algorithm can maintain a coloring of the network graph as (potentially many) edges are added or deleted. The maintained coloring is always proper; it may become partial upon updates, i.e., some nodes may temporarily lose their colors, but quickly converges to a full, proper coloring. Concretely, each insertion and deletion causes at most $O(1)$ nodes to become uncolored, but this is resolved within $O(\\log n)$ rounds with high probability (e.g., in the absence of further updates nearby--the precise guarantee is stronger, but technical). Importantly, the algorithm incurs only $O(1)$ expected message complexity and computation per update.","short_abstract":"We present a simple randomized algorithm that can efficiently maintain a $(Δ+1)$ coloring as the graph undergoes edge insertion and deletion updates, where $Δ$ denotes an upper bound on the maximum degree. A key advantage is the algorithm's ability to process many updates simultaneously, which makes it naturally adapta...","url_abs":"https://arxiv.org/abs/2512.09218","url_pdf":"https://arxiv.org/pdf/2512.09218v1","authors":"[\"Mohsen Ghaffari\",\"Jaehyun Koo\"]","published":"2025-12-10T01:02:20Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}