2022/04/23 by Bradshaw, Peter
#05C15 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2204.10968
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)) (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.