# How to find chromatic number of the hypercube $Q_n$?

How to find chromatic number the hypercube $Q_n$?

I know $\chi(Q_2)$=2 , $\chi(Q_3)$=2 , $\chi(Q_4)$=4

-
What is $Q_n{}$? – Chris Eagle Nov 2 '12 at 17:38
The $n$-cube graph. – user02138 Nov 2 '12 at 17:39

## 2 Answers

Every hypercube is bipartite (and so the chromatic number is always 2). To see this, let $A$ be the set of all strings having an odd number of 1-bits and $B$ be the set of all strings having an even number of 1-bits. Since two strings are adjacent if and only if they differ in exactly one bit, it follows that there can be no edges between two vertices of $A$ or between two vertices of $B$.

-

$\chi(Q_4)\ne4$.

HINT: The vertex set of $Q_n$ is $\{0,1\}^n$. For $v=\langle b_1,\dots,b_n\rangle\in\{0,1\}^n$ let $c(v)=\left(\sum_{k=1}^nb_k\right)\bmod 2$.

-