Simple, Deterministic, Constant-Round Coloring in the Congested Clique
Artur Czumaj, Peter Davies, Merav Parter · 2020
We settle the complexity of the (Δ + 1)-coloring and (Δ + 1)-list coloring problems in the CONGESTED CLIQUE model by presenting a simple deterministic algorithm for both problems running in a constant number of rounds. This matches the complexity of the recent breakthrough randomized constant-round (Δ + 1)-list coloring algorithm due to Chang et al. (PODC'19), and significantly improves upon the state-of-the-art O(log Δ)-round deterministic (Δ + 1)-coloring bound of Parter (ICALP'18).