Improved Deterministic $(\Delta +1)$-Coloring in Low-Space MPC

Artur Czumaj, Peter Davies, Merav Parter

We present a deterministic $O(\log \log \log n)$-round low-space Massively Parallel Computation (MPC) algorithm for the classical problem of $(\Delta +1)$-coloring on $n$-vertex graphs.…