Cooperative colorings of hypergraphs

Abstract

Given a class $\mathcal{H}$ of $m$ hypergraphs $H_1,H_2,\dots ,H_m$ with the same vertex set $V$, a cooperative coloring of them is a partition $\{I_1,I_2,\dots ,I_m\}$ of $V$ in such a way that each $I_i$ is an independent set in $H_i$ for $1\le i\le m$. The cooperative chromatic number of a class $\mathcal{H}$ is the smallest number of hypergraphs from $\mathcal{H}$ that always possess a cooperative coloring. For the classes of $k$-uniform tight cycles, $k$-uniform loose cycles, $k$-uniform tight paths, and $k$-uniform loose paths, we find that their cooperative chromatic numbers are all exactly two utilizing a new proved set system partition theorem, which also has its independent interests and offers a broader perspective. For the class of $k$-partite $k$-uniform hypergraphs with sufficient large maximum degree $d$, we prove that its cooperative chromatic number has lower bound $\hat{I}\text{c◯}({\log }_{k}d)$ and upper bound $\text{O}{\left(\frac{d}{\ln d}\right)}^{\frac{1}{k-1}}$.