Skip to main content

Research Repository

Advanced Search

Optimal (degree+1)-Coloring in Congested Clique

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

Optimal (degree+1)-Coloring in Congested Clique Thumbnail


Sam Coy

Artur Czumaj

Gopinath Mishra

Kousha Etessami

Uriel Feige

Gabriele Puppis


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.


Coy, S., Czumaj, A., Davies, P., Mishra, G., Etessami, K., Feige, U., & Puppis, G. (in press). Optimal (degree+1)-Coloring in Congested Clique. .

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
Publisher URL


Accepted Conference Proceeding (903 Kb)

Publisher Licence URL

Copyright Statement
© Sam Coy, Artur Czumaj, Peter Davies, and Gopinath Mishra;<br /> licensed under Creative Commons License CC-BY 4.0<br /> 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023).

You might also like

Downloadable Citations