Skip to main content

Research Repository

Advanced Search

Optimal (degree+1)-Coloring in Congested Clique

Coy, Sam; Czumaj, Artur; Davies, Peter; Mishra, Gopinath

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.

Presentation Conference Type Conference Paper (Published)
Conference Name ICALP 2023: 50th EATCS International Colloquium on Automata, Languages and Programming
Start Date Jul 10, 2023
End Date Jul 14, 2023
Acceptance Date Apr 21, 2021
Online Publication Date Jul 5, 2023
Publication Date 2023
Deposit Date May 16, 2023
Publicly Available Date May 16, 2023
Publisher Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Volume 261
Pages 99:1-99:20
Series Title Leibniz International Proceedings in Informatics (LIPIcs)
Book Title 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
ISBN 9783959772785
Public URL
Publisher URL


You might also like

Downloadable Citations