# Distributed Coloring of Hypergraphs

For any integer r≥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 poly(log log n)-round randomized LOCAL algorithm that computes a {\displaystyle {\mathcal O(Δ1/(r−1))-coloring w.h.p. This is tight up to polynomial factors of the time complexity as Ω(logΔlog n) distributed rounds are necessary for even obtaining a Δ-coloring, where Δ is the maximum degree, and tight up to logarithmic factors of the number of colors, as Θ((Δ/logΔ)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.

## History

## Primary Research Area

- Algorithmic Foundations and Cryptography

## Name of Conference

Structural Information and Communication Complexity (SIROCCO)## Volume

13892## Page Range

89-111## Publisher

Springer Nature## Open Access Type

- Not Open Access