Question 142
Suppose $G$ is a graph with chromatic number $n$. Suppose there exist $k$ graphs $G_{1}, G_{2}, \ldots, G_{k}$ having the same vertex set as $G$ such that $G_{1} \cup G_{2} \cup \cdots \cup G_{k}=G$ and each $G_{i}$ has chromatic number at most $2$. Show that $k \geq \left\lceil \log_{2}(n) \right\rceil$, and show that one can always find such a decomposition of $G$ into $\left\lceil \log_{2}(n) \right\rceil$ graphs.