Hypergraph cooperative coloring

doi:10.1016/j.dam.2026.04.010

Hypergraph cooperative coloring

2026-09-15

0

PRE

AI

DOI：10.1016/j.dam.2026.04.010

Original

Original request for help

Save

Abstract

En 中文

For a class H of m hypergraphs {H1, H2, ... , Hm} sharing a common vertex set V, a cooperative coloring is a partition {I1,I2,... , Im} of V where each Ii is an independent set in Hi for 1 <= i <= m. Let mk(d) denote the minimum number of k-uniform hypergraphs on a shared vertex set, each with maximum degree at most d, that are guaranteed to admit a cooperative coloring. We first prove mk(d) = Theta(dk-1 1 ) for all integers k >= 2. In a distinct line of inquiry, it is known that three graph cycles on the same vertex set admit a cooperative coloring, though their result lacks a combinatorial proof. In contrast, for k-uniform tight (or loose) cycles with k >= 3, we provide a combinatorial proof that two such cycles on the same vertex set possess a cooperative coloring. This proof relies on a newly established set partition theorem, which is of independent interest and provides broader theoretical insights. (c) 2026 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

Keywords:

Cooperative coloring

Hypergraph

Set partition

Hypergraph cooperative coloring

Abstract

Journal

Organization