Let $bp(G)$ be the number of complete bipartite graphs needed to partition the edge set of G. This means, $ \forall e \in E(G) $, e is in exactly 1 complete bipartite graph. Now, how to prove bp(G) $ \geq \log_{2}(\chi(G)) $ ?
Some things I thought of is that we can consider $ V_{i} $ the independence sets of G that form the $ \chi(H) $ colouring of $G$. Now. $ \forall i, j, i \neq j $, $ V_{i} $ and $ V_{j} $ share at least 1 edge. If we view $ V_{i} $ as a vertex each, we get a complete graph. Also, consider any 1 of the bipartite graph $(A \cup B, E)$, the set of colors of the vertices in A is disjoint with the set of colors of the vertices in $B$. But still I cannot get any progress.
Best Answer
We use induction on $\chi(G)$. I'll let you handle the base cases yourself.
Let $\chi(G) = k\geq 3$ and let \begin{equation*} C_i:=\{v \in V(G) \mid \text{ the colour used for $v$ is $i$ }\}, \end{equation*} and $\{C_1, C_2, \dots, C_{k} \}$ be the disjoint collection of colour classes of $G$. Let $I = \{1, \dots, k\}$ be an indexing set for colours used in the graph. Let $\mathcal{H} = \{H_1, H_2, \dots, H_{n} \}$ be the minimum family of complete bipartite graphs covering $E(G)$.
By minimiality of $\mathcal{H}$, each $H_i \in \mathcal{H}$ must contain at least one edge. Choose $H_1 \in \mathcal{H}$. Now, $V(H_1) \subsetneq C_i$ for any $i$, since any subset of $C_i$ is independent, and $H_1$ has an edge. Let $H_1 = (A, B)$ be the bipartition of $H_1$. We can further say that the colours of vertices in $A$ and $B$ must be disjoint, since $H_1$ is a complete bipartite graph. More precisely, there exists $S, T \neq \varnothing \subseteq I$ such that $S \cup T = I, S \cap T = \varnothing$ and $V(A) \subseteq \bigcup_{\alpha \in S} C_{\alpha}$ and $V(B) \subseteq \bigcup_{\beta \in T} C_{\beta}$.
Now, there either exists edges between vertices in $\bigcup_{\alpha \in S} C_{\alpha}$ or $\bigcup_{\beta \in T} C_{\beta}$ (why?). These edges are not covered by $E(H_1)$ (why?). The subgraphs induced by $\bigcup_{\alpha \in S} C_{\alpha}$ and $\bigcup_{\beta \in T} C_{\beta}$ have chromatic number $|S|$ and $|T|$ respectively (why?). By induction, $\bigcup_{\alpha \in S} C_{\alpha}$ requires at least $\log_2(|S|)$ complete bipartite graphs to cover its edges, and $\bigcup_{\beta \in T} C_{\beta}$ requires at least $\log_2(|T|)$ complete bipartite graphs to cover its edges. Combined with $H_{1}$, we see that, $$ bp(G) \geq \max\{\log_2(|S|), \log_2(|T|)\} + 1 $$ Yet either $|S|$ or $|T|$ are $\geq k/2$, so we have, \begin{align*} bp(G)&\geq \log_2\left(\frac{k}{2} \right) + 1 \\ &\geq \log_2(k) - \log_2(2) + 1 \\ &\geq \log_2(k). \end{align*}