Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How to find chromatic number the hypercube $Q_n$?

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

share|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
add comment

2 Answers

up vote 8 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|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

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.