Like Tree1Likes
  • 1 Post By anduril462

Graph χ(G), ω(G) and g(G)

This is a discussion on Graph χ(G), ω(G) and g(G) within the Tech Board forums, part of the Community Boards category; Studying for exams, we have an example with this graph (pic). I claimed that χ(G) = 4, ω(G) = 5 ...

  1. #1
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694

    Graph χ(G), ω(G) and g(G)

    Studying for exams, we have an example with this graph (pic). I claimed that χ(G) = 4, ω(G) = 5 and g(G) =5. Another guy, who is always trying to show off, says that this is incorrect. The good news is that I feel he is right. The bad news are that I can not find the answer.
    Of course he didn't tell me the answer when I asked him. ( I don't really know if he knows ..)
    So the unknows are, χ(G), ω(G) and g(G).
    Does anybody know? I really want to find them!

    Name:  G.png
Views: 410
Size:  16.3 KB
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,676
    My graph theory is a bit rusty. What are the functions χ(G), ω(G) and g(G)?

  3. #3
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    Glad you asked. I tought I should write them.

    G(g) is the length of the smallest cycle in the graph. If you have two cycles for example in the graph with length 15 and 16, then the girth is the min, thus 15.

    ω(G) is the clique number of the graph. This is the max complete subgraph of the graph.
    Formally : The clique number of a graph G, denoted by !(G), is the maximum k such that Kk  G.

    As for the chromatic number, nevermind, I think it is ok.
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  4. #4
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    No! The chromatic number is 3!!!! And the girth is 5. I am sure about it.

    But what is the clique number??? I had said 5, but I am not sure
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  5. #5
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    Ok, solution given by a student from Greece in facebook. This is the Petersen=s graph. My last post is ok, but the clique number is two! I was wrong in that!
    PetersenGraph

    So, user from Long Beach, do you agree that χ(G) = 3, ω(G) = 2 and g(G) =5 ??
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  6. #6
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,676
    Name:  G.png
Views: 191
Size:  26.9 KB
    I labeled the nodes to make my explanation easier.

    You do indeed have a Petersen graph, though the inner part is rotated a bit from the examples online. The nice thing about this graph is that it's symmetrical. That means you can (at least in some cases) examine just one of the outer nodes and one of the inner nodes, so you don't have to try every single possibility. The graph is also small enough for you to figure these out by hand. I agree with the numbers, but I'll explain how I figured it out.

    Girth I checked manually, with a sort of breadth-first approach, and took advantage of symmetry.
    Distance from A (from node -> to node)
    Code:
    A->B 1
    A->E 1
    A->G 1
    B->C 2
    B->H 2
    E->D 2
    E->F 2
    G->I 2
    G->J 2
    C->D 3
    C->I 3
    H->F 3
    H->J 3
    ...
    You could carry that on until you map all paths back to A, and work backwards though the list, picking the lowest cost routes to each node. I actually stopped early because I realized that, from node C, which was distance 2 from A, I could get to I, which was also distance 2 from A. There was just the cost of moving from C to I, which was cost 1. There was no way to get from a vertex that was distance 2 from A, to a vertex that was distance 1 from A. That gave me g(G) = dist(A->C) + dist(A->I) + dist(C->I) = 2+2+1 = 5. The fact that every node was reachable (not necessarily in a cycle) from A in at most 2 edges made me realize that in this graph, no node is more than 2 edges away from any other node. I didn't know if I would need that info yet, but it couldn't hurt.​ that is not necessary, since each cycle from A includes at least one of the inner nodes (F-J)

    Next, onto clique number. It helped me immensely to look at the chart of complete graphs here. I could easily rule out the larger cliques (5 and above), since each node would need ω(G)-1 edges, and the nodes in this graph all have only 3 edges. That means the biggest clique possible might be 4. But we see that, for any clique size 3 or larger, there must be a triangle in the graph. This graph has no triangle. Thanks to symmetry, this is easy to check. Take node A, it has 3 neighbors, B, E and G. To make a triangle, two of those neighbors must share an edge. Similarly, examining an "inner" node, F, you find that none of its neighbors (E, H or I) share an edge. Thus, the best we can do is ω(G) = 2.

    Lastly, is the chromatic number. I assume you're talking about vertex coloring since edge coloring is usually specified explicitly. There happens to be a fancy formula for calculating the number of t-colorings for graphs, where t is the number of different colors you use. Wikipedia shows the formula for Petersen graphs here. You can see that if t is 0, 1 or 2, one of the first terms will be 0, and there will be no colorings. Plugging 3 into the equation yields a positive result (120 different colorings I think it was), so χ(G) = 3. Intuitively, you can rule out χ(G) = 1, since there are nodes with neighbors. Also, you can rule out χ(G) = 2, by trial and errors, using alternating colors. So A is red, B, E and G are green. Then their neighbors (C, D, F, I and J) are red again. But C and D are themselves neighbors, and are both red, thus the graph is not 2-colorable. If you try 3 colors, you should be able to do it pretty easily.
    manasij7479 likes this.

  7. #7
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    The girth and the chromatic number was understood by me in post #4. The girth was actually ok from the start.

    The clique number, I have to admit, was not clear at all for me.

    So, you claim that given a graph G, if there is no triangle formed in it, then it has ω(G) <= 2 ?

    PS - Nice explanation
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  8. #8
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,676
    Quote Originally Posted by std10093 View Post
    The girth and the chromatic number was understood by me in post #4. The girth was actually ok from the start.
    Ahh, yeah, I had started on my explination before you wrote posts #4 and 5, so I just continued with it, regardless. Hopefully somebody else finds it useful.

    The clique number, I have to admit, was not clear at all for me.

    So, you claim that given a graph G, if there is no triangle formed in it, then it has ω(G) <= 2 ?
    Yes, that is what I claim. A clique is a complete subgraph. Complete means every node in the subgraph shares an edge with every other node in the subgraph. A complete graph with 3 vertices forms a triangle. A complete graph with more than 3 vertices still contains triangles, so it is ω(G) >= 3 (actually, any complete graph is ω(G) = |V| (number of vertices)). Thus, if there are no triangles in your graph (if it is triangle-free), then it can not have any 3-cliques (or larger cliques). Since a triangle is a complete 3-vertex graph (or subgraph in this case), by definition of clique, the graph would be at least 3-clique (some graphs may have triangles, but have a larger maximum clique number).

    PS - Nice explanation
    Thanks. And thanks for posting this, it's nice to get a break from the tedium of fixing newbie's scanf format specifier mistakes and the like.

  9. #9
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    1 - yeah, I wrote them rapidly

    2 - Perfect. I will refer to this, as part of what I read before going to exams

    3 - Well, I am 3rd year students, as my name states ;p

    Thanks again!
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. bar graph help
    By Sixx in forum C Programming
    Replies: 2
    Last Post: 10-30-2012, 05:37 PM
  2. Graph - Help!! :(
    By Zeldic in forum C++ Programming
    Replies: 6
    Last Post: 06-02-2010, 09:15 AM
  3. graph.h
    By spime in forum C Programming
    Replies: 10
    Last Post: 11-04-2008, 02:22 PM
  4. Graph
    By fkheng in forum C Programming
    Replies: 8
    Last Post: 07-05-2003, 11:57 PM
  5. Graph possible for c++ ??
    By joeyzt in forum C++ Programming
    Replies: 2
    Last Post: 06-28-2003, 09:00 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21