Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is there any theorem that apllies to non simple cycles and chromatic number? For example we know that x(G)=2 if G does not contains odd cycles. What about a non-simple cycle that contains odd cycles. E.g A square and a triangle having a common vertex is (n=6,3-chromatic) A petagon and a triangle having a common vertex is (n=7, 3-chromatic) Is any proof for saying that at least 3 colors are needed to use for non simple cycles that contain an odd cycle?And is that related to the number of its vertices? PS it is not a homework but basic to use it for one Thnx in advance

share|improve this question
add comment

1 Answer

It is a well known theorem that a graph is bipartite (2 colourable) if and only if all its cycles are of even length.

So if you have a graph which has an odd cycle, it will require at least 3 colours.

For instance you can find a proof here: http://books.google.com/books?id=aR2TMYQr2CMC&pg=PA18

In any case, for a simpler proof of: To a cycle of odd length, to each vertex you cannot assign one of two colours so that adjacent vertices get different colours

Say you try and walk around the cycle. Each step you take, you flip the colour. So to get back to the original vertex, you need to take an even number of steps. That is not possible with an odd cycle. So you need at least 3 colours.

Note that if the graph you have is exactly two cycles which share exactly one vertex (like in your examples), then that graph is 3 colourable.

This is because a cycle is 3 colourable, even if you pre-assign a vertex with a given colour. You colour one cycle first, then based on the colour of the common vertex, you colour the other cycle.

In general, though, determining the chromatic number of a graph is a hard problem. In fact, it is NP-Complete.

share|improve this answer
    
Thnx Moron,but is there any theorem to prove that? –  Nick Mar 8 '11 at 18:46
    
@Nick: This is one of the basic facts and you should find it any decent book on graph theory. –  Aryabhata Mar 8 '11 at 18:48
    
Thnx it was so simple so it is not vertex related for n>= 3.You can have a n=2k graph having an odd cycle and still be 3-chromatic. so in conclusion for every n>=3 if the graph contains an odd cycle is 3-chromatic. –  Nick Mar 8 '11 at 19:09
2  
@Nick: Not every graph with odd cycles is 3-chromatic. Every graph with odd cycles requires at least 3 colors, but 3 might not be enough. The chromatic number can be arbitrarily large. –  aaron Mar 8 '11 at 19:28
    
@Nick: As aaron says, your conclusion is wrong. I have edited the answer to give more information. –  Aryabhata Mar 8 '11 at 23:51
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.