1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook