Optimal (degree+1)-Coloring in Congested Clique

Abstract. We consider the distributed complexity of the ( degree + 1 )-list coloring problem, in which each node [Formula: see text] of degree [Formula: see text] is assigned a palette of [Formula: see text] colors, and the goal is to find a proper coloring using these color palettes. The ( degree + 1 )-list coloring problem is a natural generalization of the classical [Formula: see text]-coloring and [Formula: see text]-list coloring problems, both being benchmark problems extensively studied in distributed and parallel computing. In this paper, we settle the complexity of the ( degree + 1 )-list coloring problem in the Congested Clique model by showing that it can be solved deterministically in a constant number of rounds.