Randomized round complexity of Δ-list-coloring
Question on randomized list-coloring round complexity · arXiv:1802.05582
Status open medium confidence
The question asks whether a randomized distributed algorithm for Delta-list-coloring can achieve round complexity without a polynomial factor in Delta, analogously to the O(log^3 n / log Delta)-round randomized algorithm of Panconesi and Srinivasan for Delta-coloring. Subsequent work has made substantial progress on randomized Delta-coloring (Ghaffari et al. 2018 reduced to O(log Delta) + 2^{O(sqrt{log log n})} rounds; a 2025 preprint further improved deterministic bounds), and a 2024 paper achieves poly-log log n rounds for Delta-coloring in CONGEST, but none of these works specifically address Delta-list-coloring (with exactly Delta colors per vertex from individual lists). The question, which concerns a strictly harder list variant, appears to remain open as of 2026.
Reviewer notes. Web searches found significant follow-up on randomized distributed Delta-coloring (not list-coloring): Ghaffari-Hirvonen 2018 (arXiv:1803.03248) achieves O(log Delta) + 2^{O(sqrt{log log n})} rounds for Delta-coloring; arXiv:2504.03080 (2025) improves deterministic bounds further; arXiv:2405.09975 (2024) achieves poly-log-log n randomized rounds for Delta-coloring in CONGEST. None of these papers address the specific question about Delta-LIST-coloring (Corollary 2.1 of the source paper). The distinction matters: standard Delta-coloring exploits graph structure globally, while Delta-list-coloring with arbitrary per-vertex palettes of size exactly Delta is strictly harder and different techniques apply. No resolution of this specific open question was found.
Context
Panconesi and Srinivasan gave a randomized $\Delta$-coloring algorithm running in $O(\log^3 n / \log \Delta)$ rounds. The paper's list-coloring extension (Corollary 2.1) achieves $O(\Delta^2 \log^3 n)$ rounds deterministically, but it is noted to be unclear whether a randomized variant can similarly remove the polynomial dependence on $\Delta$.
Notes. Implicit question in prose: "it is not clear whether we can similarly avoid the multiplicative factor polynomial in $\Delta$ in a randomized version of our algorithm"; PDF source.
Source paper
Distributed coloring in sparse graphs with fewer colors
Pierre Aboulker, Marthe Bonamy, Nicolas Bousquet, Louis Esperet · 2018-12-19
https://arxiv.org/abs/1802.05582
PDF source