# Math Help - Coloring Vertices in Graph Theory

1. ## 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.

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