Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Chromatic number of the n-cube

  1. Jun 3, 2009 #1
    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. jcsd
  3. Jun 3, 2009 #2
    Empirical evidence suggests it's just 2.
  4. Jun 3, 2009 #3
    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.
  5. Jun 3, 2009 #4
    Oh ya, thanks.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Chromatic number of the n-cube
  1. Labeling an n-cube (Replies: 3)