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.
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)