# Chromatic number of the n-cube

1. Jun 3, 2009

### Dragonfall

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.

2. Jun 3, 2009

### Dragonfall

Empirical evidence suggests it's just 2.

3. Jun 3, 2009

### Moo Of Doom

The n-cube is bipartite, so its chromatic number is 2. If we label the vertices canonically with vectors in $$\{0, 1\}^n$$, 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. Jun 3, 2009

### Dragonfall

Oh ya, thanks.