Results 1 to 6 of 6

Math Help - colouring vertices in graph theory

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    11

    Red face colouring vertices in graph theory

    Compare the upper bound for the chromatic number given by Brooks' theorem with the correct value for
    i) the Petersen Graph
    ii) the k-cube Qk

    the answer is:

    i) upper bound = 3, chromatic number = 3
    ii) upper bound = k, chromatic number = 2.

    but I don't know how to explain why?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    First a general remark. Not everybody studied Brooks' theorem and related concepts in college, but most people in this subforum know about graphs and coloring. If it is reasonable to think that the cost of learning about the concepts from your particular problem is not too high, and if you think you can benefit from the "common mathematical knowledge" of many smart(er than me) people on this forum, then it may be worth giving the definitions of the concepts involved and maybe giving some standard online reference. Of course, if it seems that "common knowledge" is not sufficient and one has to be an expert in those particular concepts, then it probably does not make sense to explain a lot, waiting for replies from people who know what you are talking about.

    The upper bound given by the Brooks' theorem is the maximum vertex degree. It's relatively easy to see from the definitions that in Peterson's graph every vertex has degree 3, and in Q_k every vertex has degree k. The 3-coloring of Peterson's graph is shown in Wikipedia. To prove that it is not 2-colorable, try to come up with a 2-coloring making only steps that are necessary (i.e., do not involve guessing the color of some vertex), and you will see that this is impossible.

    The graph Q_k is bipartite as described in Wikipedia, and it's also relatively easy to see why. Therefore, its chromatic number is 2.

    Is it possible that I misunderstood your question and that you were asking not why the numbers are what they are, but why the upper bound is tight for Peterson's graph and not tight for Q_k?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2009
    Posts
    11
    well, no it isn't clear to me why, that's why I posted in the forum. So I could get a clearer understanding beyond wikipedia.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    I am not sure I can say something beyond Wikipedia, even in this particular area. But did the post above answer your questions? If not, could you say which part you don't understand and why?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2009
    Posts
    11

    hello

    I've got it now. the Petersen graph is a cubic graph, has degree 3. We can see that the outer 5-cycle in the Petersen graph cannot by coloured with just 2 colours, thus the chromatic polynomial is 3.

    I'm slowly getting it
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    That's right. (I am not sure about the word "cubic": it does not mean that the chromatic polynomial of Petersen graph is cubic, does it?)

    Concerning the cube graph Q_k, one of the definitions is that it is the set of sequences of length k where each element is 0 or 1. E.g., the 3-dimensional cube is has 8 vertices: (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1). If one imagines a usual 3-dimensional coordinate system with axes (x,y,z), then those 8 points would indeed form a cube.

    A vertex (x,y,z) has an edge to (x',y',z') iff these two triples differ in exactly one component. For example, there is an edge between (0,1,0) and (0,1,1), but there is no edge between (0,1,0) and (0,0,1): that would be a diagonal in one of the cube's surfaces. So, each vertex (x,y,z) has exactly three neighbors obtained by changing x, y, or z (but only one of those).

    It is clear that two connected vertices have the number of 1's that differ by 1: if one has 0 in k-th position, then it's neighbor has 1. Therefore, if the number of 1's in one vertex is even, then that number of any of its neighbors is odd. Thus, we can divide vertices into even and odd, so that no two even and no two odd vertices are connected. This means that the graph is bipartite, and its chromatic number is 2.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph Theory- Edge Colouring
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 4th 2011, 01:20 AM
  2. [SOLVED] Graph Theory Question - Vertices
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 13th 2010, 08:47 AM
  3. Graph theory - colouring
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 17th 2010, 09:26 PM
  4. Coloring Vertices in Graph Theory
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 29th 2009, 07:04 AM
  5. Replies: 5
    Last Post: June 22nd 2008, 11:20 PM

Search Tags


/mathhelpforum @mathhelpforum