Cooperative colorings of forests

Abstract

Given a family $\mathcal{G}$ of graphs spanning a common vertex $V$, a cooperative coloring of $\mathcal{G}$ is a collection of one independent set from each graph of $\mathcal{G}$ such that the union of these independent sets equals $V$. We prove that when $d$ is large, 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.

7 pages