Optimal (degree+1)-Coloring in Congested Clique

Coy, Sam; Czumaj, Artur; Davies, Peter; Mishra, Gopinath; Etessami, Kousha; Feige, Uriel; Puppis, Gabriele

Abstract

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.

Citation

Coy, S., Czumaj, A., Davies, P., Mishra, G., Etessami, K., Feige, U., & Puppis, G. (in press). Optimal (degree+1)-Coloring in Congested Clique. . https://doi.org/10.4230/lipics.icalp.2023.99

• Conference Name: ICALP 2023: 50th EATCS International Colloquium on Automata, Languages and Programming
• Conference Location: Paderborn, Germany
• Start Date: Jul 10, 2023
• End Date: Jul 14, 2023
• Acceptance Date: Apr 21, 2021
• Deposit Date: May 16, 2023
• Publicly Available Date: May 16, 2023
• Publisher: European Association for Theoretical Computer Science
• Pages: 99:1-99:20
• DOI: https://doi.org/10.4230/lipics.icalp.2023.99
• Publisher URL: https://dblp.org/db/conf/icalp/index.html