Efficient Deterministic Distributed Coloring with Small Bandwidth

We show that the $(degree+1)$-list coloring problem can be solved deterministically in $O(D cdot log n cdotlog^2Delta)$ rounds in the CONGEST model, where $D$ is the diameter of the graph, $n$ the number of nodes, and $Delta$ the maximum degree. Using the recent polylogarithmic-time deterministic network decomposition algorithm by Rozhov{n} and Ghaffari [STOC 2020], this implies the first efficient (i.e., $polylog n$-time) deterministic CONGEST algorithm for the $(Delta+1)$-coloring and the $(mathit{degree}+1)$-list coloring problem. Previously the best known algorithm required $2^{O(sqrt{log n})}$ rounds and was not based on network decompositions. Our techniques also lead to deterministic $(mathit{degree}+1)$-list coloring algorithms for the congested clique and the massively parallel computation (MPC) model. For the congested clique, we obtain an algorithm with time complexity $O(logDeltacdotloglogDelta)$, for the MPC model, we obtain algorithms with round complexity $O(log^2Delta)$ for the linear-memory regime and $O(log^2Delta + log n)$ for the sublinear memory regime.