Cooperative coloring of some graph families

Abstract

In a family $G_1,G_2,\dots ,G_m$ of graphs sharing the same vertex set $V$, a cooperative coloring involves selecting one independent set $I_i$ from $G_i$ for each $i\in \{1,2,\dots ,m\}$ such that ${\bigcup }_{i=1}^m{I}_i=V$. For a graph class $\mathcal{G}$, let $m_{\mathcal{G}}(d)$ denote the minimum $m$ required to ensure that any graph family $G_1,G_2,\dots ,G_m$ on the same vertex set, where $G_i\in \mathcal{G}$ and $\Delta (G_i)\le d$ for each $i\in \{1,2,\dots ,m\}$, admits a cooperative coloring. For the graph classes $\mathcal{T}$ (trees) and $\mathcal{W}$ (wheels), we find that $m_{\mathcal{T}}(3)=4$ and $m_{\mathcal{W}}(4)=5$. Also, we prove that $m_{{\mathcal{B}}^{\ast }}(d)=O({\log }_{2}d)$ and $m_{\mathcal{L}}(d)=O\left(\frac{\log d}{\log \log d}\right)$, where ${\mathcal{B}}^{\ast }$ represents the class of graphs whose components are balanced complete bipartite graphs, and $\mathcal{L}$ represents the class of graphs whose components are generalized theta graphs.