2026-07-25T06:17:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18098 2024-03-06T11:01:00Z ddc:004 open_access

Optimal (Degree+1)-Coloring in Congested Clique Coy, Sam Czumaj, Artur Davies, Peter Mishra, Gopinath Distributed computing graph coloring parallel computing 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sam Coy and Artur Czumaj and Peter Davies and Gopinath Mishra 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.46 urn:nbn:de:0030-drops-180987 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.46 eng https://creativecommons.org/licenses/by/4.0/legalcode