Coloring Vertices in Graph Theory

• November 28th 2009, 08:16 PM
tigertina
Coloring Vertices in Graph Theory
Compare the upper bound for the chromatic number given by Brooks' Theory with the correct value for the k-cube Qk.

the upper bound is k and the chromatic number is 2.

What I'm trying to figure out is why the chromatic number is 2 for the k-cube Qk graph.

• November 29th 2009, 06:04 AM
awkward
Quote:

Originally Posted by tigertina
Compare the upper bound for the chromatic number given by Brooks' Theory with the correct value for the k-cube Qk.

the upper bound is k and the chromatic number is 2.

What I'm trying to figure out is why the chromatic number is 2 for the k-cube Qk graph.

This seems to work:

If a typical vertex is $(x_1, x_2, x_3, \dots , x_k)$ where each $x_i$ is 0 or 1, divide the vertices into two groups (colors) based on the parity of $x_1 + x_2 + x_3 + \dots + x_k$.