Cooperative Colorings of Forests

Abstract

Given a family $\mathcal G$ of graphs spanning a common vertex set $V$, a cooperative coloring of $\mathcal G$ is a collection of one independent set from each graph $G \in \mathcal G$ such that the union of these independent sets equals $V$. We prove that for large $d$, there exists a family $\mathcal G$ of $(1+o(1)) \frac{\log d}{\log \log d}$ forests of maximum degree $d$ that admits no cooperative coloring, which significantly improves a result of Aharoni, Berger, Chudnovsky, Havet, and Jiang (Electronic Journal of Combinatorics, 2020). Our family $\mathcal G$ consists entirely of star forests, and we show that this value for $|\mathcal G|$ is asymptotically best possible in the case that $\mathcal G$ is a family of star forests.