Cooperative colorings of forests

Peter Bradshaw¹

¹Simon Fraser University

The electronic journal of combinatorics, Tome 30 (2023) no. 1

Résumé

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.

Détail

DOI : 10.37236/11461

Classification : 05C15, 05C75
Mots-clés : star forests