Graphs: How to prove that chromatic number of graph $G$ is $2^k$ if and only is $G$ is union of $k$ bipartite graphs?

Question

Prove that chromatic number of graph $G$ is $2^k$ if and only is $G$ is union of $k$ bipartite graphs.

Any hints how to prove this statement?

Answer 1

The statement is incorrect and should presumably be "$G$ is $2^k$-colourable if and only if it is a union of $k$ bipartite graphs".

Hint: fix a proper $2^k$-colouring, and think of the colours as binary strings of length $k$. For each position in the strings, consider what would happen if you $2$-coloured the vertices based on that position only.

Answer 2

Since the last answer does not provide any elaborations on the hint, here's a detailed explanation-

Let's say we have $k$ bipartite graphs, $G_i=(V_i,E_i)$, $1\le i\le k$. Let the partites of $G_i$ be $R_i$ and $B_i$ (and so, each element of $V_i$ is in either one of them). Also, let $V=\cup_{i=1}^k V_i$. Now, we replace all $G_i=(V_i,E_i)$ by $G_i=(V,E_i)$ where the elements of $V\setminus V_i$ are all kept in the partite $R_i$. It is clear that no generality is lost in this replacement process.

Now, $\forall i\in \{1,2,\dots ,k\}$, any element of $V$ (i.e., any vertex of the graph) belongs to exactly one of $B_i$ or $R_i$. So, all such elements can be labelled with a $k$-string of $r$'s and $b$'s according to this scheme- the $i$-th position will have an $r$ or a $b$ if the vertex is present in $R_i$ or $B_i$ respectively. Since each label is a $k$-string and each position in the string has exactly two choices, there are $2^k$ such combinations.

This completes one part of the proof.

---

Now, let us have a $2^k$ colourable graph $G$ coloured with $2^k$ colours. We want to show that $G$ is a union of $k$ bipartite graphs. To do this, we will almost do a reverse of what we did in the last part.

Let us name all the colours as binary $k$-strings of $r$'s and $b$'s. Now, let us consider pairs of sets, $R_i$ containing all the vertices with $r$ in the $i$-th index, and $B_i$ containing all vertices with $b$ in the $i$-th index. Note that $R_i$ and $B_i$ would be a pair of partites if there are no edges inside each $R_i$ or $B_i$. So, let us consider the $k$ bipartite graphs $G_i$, $i\in\{1,2,\dots ,k\}$ with elements of $R_i$ and $B_i$ as the vertices, and only those edges that connect between $R_i$ and $B_i$. This gives us a union of $k$ bipartite graphs.

It remains to show that edges that we "cleared" from the $R_i$'s and the $B_i$'s have been counted atleast once in the final union. Notice that same labels will never be connected due to properties of graph colouring, and hence an edge (say $e$) can only connect two different labels. Now, two different labels must differ in atleast one position, say the $j$-th position. Thus, $e$ will be counted in the union whenever we count the graph $G_j$.

This completes the proof.