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
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.