Optimal (degree+1)-Coloring in Congested Clique

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

doi:10.4230/LIPIcs.ICALP.2023.46

Optimal (degree+1)-Coloring in Congested Clique

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

Authors

Sam Coy

Artur Czumaj

Dr Peter Davies-Peck peter.w.davies@durham.ac.uk
Assistant Professor

Gopinath Mishra

Contributors

Kousha Etessami
Editor

Uriel Feige
Editor

Gabriele Puppis
Editor

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). Optimal (degree+1)-Coloring in Congested Clique. In K. Etessami, U. Feige, & G. Puppis (Eds.), 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) (99:1-99:20). https://doi.org/10.4230/LIPIcs.ICALP.2023.46

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

Files

Published Conference Proceeding (903 Kb)
PDF

Licence
http://creativecommons.org/licenses/by/4.0/

Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/

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