Cooperative colorings of trees and of bipartite graphs

Abstract

Given a system $(G_1,\dots ,G_m)$ of graphs on the same vertex set $V$, a cooperative coloring is a choice of vertex sets $I_1,\dots ,I_m$, such that $I_j$ is independent in $G_j$ and ${\bigcup }_{j=1}^m{I}_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 $\hat{I}\text{c◯}(\log \log d)\le m_{\mathcal{T}}(d)\le O(\log d)$ and $\hat{I}\text{c◯}(\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.

8 pages, 2 figures, accepted to the Electronic Journal of Combinatorics, corrections suggested by the referees have been incorporated