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

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?

Solution 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.

Mistake in proof of Lemma 2.3 in Chapter 3 of Stein and Shakarchi's Fourier Analysis

Show that if $p$ is a odd prime number, then $p\mid2^{p-1} + (p -1)!$ [duplicate]

Uniqueness of a function that satisfies a condition

Why is $\mathcal{P}(A\cup B) \not\subset \mathcal{P}(A)\cup\mathcal{P}(B)$?

Conditional Expectation: $E(X | \mathcal{G})$ is a function, while $EX$ is a constant?

If $f : A \to B$ and $B$ is countable, given that $f$ is surjective, $A$ is countable.

Showing that $\lim \sup\limits_{\gamma} \left \|a - a e_{\gamma} \right \| \leq \|a - b\|$ for all $a \in A$ and $b \in J.$

How to deploy phpadmin in Azure Kubernetes?

Get the index of duplicate values except the first

deactivate/comment out makros in a lot of excel files

awk/bash append headers in many csv files

Output of multiple values from the database [duplicate]

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

Solution 1:

Related

Recent Posts