Optimal (degree+1)-Coloring in Congested Clique

SIAM Journal on Computing 2026 Open access

Read full text
Authors: Sam Coy, Artur Czumaj, Peter Davies, Gopinath Mishra
DOI: 10.1137/24m163092x
Cited by: 1
References: 46

Abstract

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

Fields of Study & Subjects

Advanced Graph Theory Research Auction Theory and Applications Scheduling and Timetabling Solutions

Publication details

Journal / source
SIAM Journal on Computing
Publisher
Society for Industrial & Applied Mathematics (SIAM)
Volume
55
Issue
4
Pages
521–559
Publication date
17 July 2026
Language
EN