Distributed coloring of hypergraphs

Duncan Adamson, Magnús M. Halldórsson, Alexandre Nolin*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution


For any integer $$r \ge 2$$, a linear r-uniform hypergraph is a generalization of ordinary graphs, where edges contain r vertices and two edges intersect in at most one node. We consider the problem of coloring such hypergraphs in several constrained models of computing, i.e., computing a partition such that no edge is fully contained in the same class. In particular, we give a $$\textrm{poly}(\log \log n)$$ -round randomized Local algorithm that computes a $$O(\varDelta ^{1/(r-1)})$$ -coloring w.h.p. This is tight up to polynomial factors of the time complexity as $$\varOmega (\log _\varDelta \log n)$$ distributed rounds are necessary for even obtaining a $$\varDelta $$ -coloring, where $$\varDelta $$ is the maximum degree, and tight up to logarithmic factors of the number of colors, as $$\varTheta ((\varDelta /\log \varDelta )^{1/(r-1)})$$ colors are necessary for existence. We also give simple algorithms that run in O(1)-rounds of the Congested Clique model and in a single-pass of the semi-streaming model.

Original languageEnglish
Title of host publicationStructural Information and Communication Complexity - 30th International Colloquium, SIROCCO 2023, Proceedings
EditorsSergio Rajsbaum, Alkida Balliu, Dennis Olivetti, Joshua J. Daymude
PublisherSpringer Science and Business Media
Number of pages23
ISBN (Electronic)9783031327339
ISBN (Print)9783031327322
Publication statusPublished - 25 May 2023
Event30th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2023 - Alcalá de Henares, Spain
Duration: 6 Jun 20239 Jun 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13892 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference30th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2023
CityAlcalá de Henares


  • Congested Clique
  • Distributed computing
  • Hypergraph coloring
  • LOCAL model


Dive into the research topics of 'Distributed coloring of hypergraphs'. Together they form a unique fingerprint.

Cite this