How to find chromatic number of the $n$-dimensional hypercube $Q_n$?

graph-theory coloring

How to find chromatic number the $n$-dimensional hypercube $Q_n$?

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


Solution 1:

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

Solution 2:

$\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$.

Related

For what value of m that the equation $y^2 = x^3 + m$ has no integral solutions? [closed]
For which values of $d<0$ , is the subring of quadratic integers of $\mathbb Q[\sqrt{d}]$ is a PID?
How is $\ln(-1) = i\pi$? [closed]
$\left \| \cdot \right \|$ is an induced norm. If $\left \| A \right \|<1$, how to show that $I-A$ is nonsingular and ...?
Show that for all real numbers $a$ and $b$, $\,\, ab \le (1/2)(a^2+b^2)$ [duplicate]
Prove that there is no element of order $8$ in $SL(2,3)$
Manifold is not orientable
Finding the dimension of $S = \{B \in M_n \,|\, AB = BA\}$, where $A$ is a diagonalizable matrix
Why $\mathbb{R}$ is a subset of $\mathbb{C}$? [duplicate]
Morphism that is not a mapping
Evaluate $\lim_{x\to 0}\frac{x-\sin x}{x\sin x}$ without to use L'Hopital
Evaluating $\lim_{n\to\infty} \frac{1^{99} + 2^{99} + \cdots + n^{99}}{n^{100}}$ using integral