Optimal (degree+1)-Coloring in Congested Clique
SIAM Journal on Computing · 31.08.2026 · 55 (4) · 521-559
DOI: 10.1137/24m163092x ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 17.07.2026. Verfasst von Sam Coy und 3 weiteren Autor:innen. Die Arbeit nennt 46 Literaturangaben. Gefördert von: Centre for Discrete Mathematics and its Applications, Simons Foundation, Engineering and Physical Sciences Research Council.
Abstract (Originalsprache)
We consider the distributed complexity of the ( degree + 1 )-list coloring problem, in which each node [Formula: see text] of degree [Formula: see text] is assigned a palette of [Formula: see text] 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 [Formula: see text]-coloring and [Formula: see text]-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.
Förderung
- Centre for Discrete Mathematics and its Applications
- Simons Foundation
- Engineering and Physical Sciences Research Council
Zitieren
APA
Coy, S., Czumaj, A., Davies, P., & Mishra, G. (2026). Optimal (degree+1)-Coloring in Congested Clique. SIAM Journal on Computing, 55(4), 521-559. https://doi.org/10.1137/24m163092x
Vancouver
Coy S, Czumaj A, Davies P, Mishra G. Optimal (degree+1)-Coloring in Congested Clique. SIAM Journal on Computing. 2026;55(4):521-559. doi:10.1137/24m163092x
BibTeX
@article{Coy2026,
author = {Coy, Sam and Czumaj, Artur and Davies, Peter and Mishra, Gopinath},
title = {Optimal (degree+1)-Coloring in Congested Clique},
journal = {SIAM Journal on Computing},
year = {2026},
volume = {55},
number = {4},
pages = {521--559},
doi = {10.1137/24m163092x}
}
EUVIMED