2023/06/21 by Coy, Sam, Czumaj, Artur, Davies, Peter +1 · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2306.12071
We consider the distributed complexity of the (degree+1)-list coloring problem, in which each node u of degree d(u) is assigned a palette of d(u)+1 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 (Δ+1)-coloring and (Δ+1)-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.