Cooperative colorings of trees and of bipartite graphs (Q2294110)

Summary: Given a system \((G_1, \ldots ,G_m)\) of graphs on the same vertex set \(V\), a cooperative coloring is a choice of vertex sets \(I_1, \ldots ,I_m\), such that \(I_j\) is independent in \(G_j\) and \(\bigcup_{j=1}^mI_j = V\). For a class \(\mathcal{G}\) of graphs, let \(m_{\mathcal{G}}(d)\) be the minimal \(m\) such that every \(m\) graphs from \(\mathcal{G}\) with maximum degree \(d\) have a cooperative coloring. We prove that \(\Omega(\log\log d) \le m_\mathcal{T}(d) \le O(\log d)\) and \(\Omega(\log d)\le m_\mathcal{B}(d) \le O(d/\log d)\), where \(\mathcal{T}\) is the class of trees and \(\mathcal{B}\) is the class of bipartite graphs.