Chromatic number of the n-cube

  • Thread starter Dragonfall
  • Start date
  • #1
1,030
4
What is the chromatic number of the n-cube? As a graph, I mean. For the square and 3-cube, for example, it's 2.
 

Answers and Replies

  • #2
1,030
4
Empirical evidence suggests it's just 2.
 
  • #3
367
1
The n-cube is bipartite, so its chromatic number is 2. If we label the vertices canonically with vectors in [tex]\{0, 1\}^n[/tex], then we can partition the vertices into those with an even number of 1's and those with an odd number of 1's.
 
  • #4
1,030
4
Oh ya, thanks.
 
Top