Results 1 to 2 of 2

Math Help - Coloring Vertices in Graph Theory

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    11

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

    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by tigertina View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph theory : coloring edges
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: January 28th 2011, 04:48 AM
  2. Graph coloring
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 2nd 2010, 11:49 AM
  3. [SOLVED] Graph Theory Question - Vertices
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 13th 2010, 07:47 AM
  4. colouring vertices in graph theory
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: December 3rd 2009, 03:53 PM
  5. Replies: 5
    Last Post: June 22nd 2008, 10:20 PM

Search Tags


/mathhelpforum @mathhelpforum