Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How to find chromatic number the hypercube $Q_n$?

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

share|cite|improve this question
What is $Q_n{}$? – Chris Eagle Nov 2 '12 at 17:38
The $n$-cube graph. – user02138 Nov 2 '12 at 17:39
up vote 10 down vote accepted

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

share|cite|improve this answer


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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.