Optimal (degree+1)-Coloring in Congested Clique

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

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. (2023, July). Optimal (degree+1)-Coloring in Congested Clique. Presented at ICALP 2023: 50th EATCS International Colloquium on Automata, Languages and Programming, Paderborn, Germany

• 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
• DOI: https://doi.org/10.4230/LIPIcs.ICALP.2023.46
• Public URL: https://durham-repository.worktribe.com/output/1134076
• Publisher URL: https://dblp.org/db/conf/icalp/index.html