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!
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
My graph theory is a bit rusty. What are the functions χ(G), ω(G) and g(G)?
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
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
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
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)
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)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 ...
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.
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
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.Originally Posted by std10093
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).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 ?
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.PS - Nice explanation
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
