Cooperative colorings of forests (Q2684895)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Cooperative colorings of forests |
scientific article |
Statements
Cooperative colorings of forests (English)
0 references
17 February 2023
0 references
Summary: Given a family \(\mathcal{G}\) of graphs spanning a common vertex set \(V\), a cooperative coloringof \(\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 \textit{R. Aharoni} et al. [Electron. J. Comb. 27, No. 1, Research Paper P1.41, 9 p. (2020; Zbl 1432.05036)]. 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.
0 references
0 references