Cooperative colorings of forests

DOI10.37236/11461arXiv2204.10968MaRDI QIDQ6397255FDOQ6397255

Authors: Peter Bradshaw 

Publication date: 22 April 2022

Abstract: Given a family $mathcalG$ of graphs spanning a common vertex $V$, a cooperative coloring of $mathcalG$ is a collection of one independent set from each graph of $mathcalG$ such that the union of these independent sets equals $V$. We prove that when $d$ is large, there exists a family $mathcalG$ of $(1+o(1))fraclogdloglogd$ 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 $mathcalG$ consists entirely of star forests, and we show that this value for $|mathcalG|$ is asymptotically best possible in the case that $mathcalG$ is a family of star forests.

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75)

This page was built for publication: Cooperative colorings of forests

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6397255)