1
$\begingroup$

So I had an exam today and one of the questions were:

G is an undirected graph, and every two of its odd-lengthed cycles have a common vertex. Prove that G is 5-colorable.

So I found this answer (which is very annoying in its simplicity and elegance): 5-color graph problem

But I would like to write what I said in the exam, and hopefully someone can reassure me, because as things stand now - I'm pretty sure I did wrong.

I said: let's remove all of the edges of the odd-lengthed cycles from G (or one of its connected components, doesn't matter). This leaves only even-lengthed cycles and simple paths, which are both 2-colorable (even when connected). Also, any odd-lengthed cycle is 3-colorable, and any "connected" odd-lengthed cycles (with a common vertex) are also 3-colorable with the same 3 colors (just start from the connected vertex and continue alternatingly). So we return the edges of the odd-lengthed cycles to the original graph, and color their vertices with 3 new colors. So we have the 2 colors from when we removed the cycles, plus the three new colors that we added.

I think I'm wrong, or at least incomplete, because I don't really show that when I return all the edges, I'm not ruining the 3+2 colors somehow.. I don't know. If anyone could either disprove or reassure me that would be great (the latter would be greater).

Thanks!

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Your 'proof' would show that any graph is 5-colorable. You found the weakness already: you cannot just 'independently' add back the old cycles: they will interfere.

$\endgroup$
3
  • $\begingroup$ But I stated that specifically such odd-lengthed cycles, i.e. of which every pair has a common vertex, only they could be 3-colorable and these won't interefere with the graph coloring. It isn't true for every graph, because when the cycles are added back, the edges in between them could cause interference. But if all the odd-cycles are "connected" this can't happen. $\endgroup$
    – Cauthon
    Jun 25, 2014 at 14:11
  • $\begingroup$ I don't really see your point. But two odd cycles can have many common vertices. There is nothing in the problem statement that says they have only one. Also if you have added back cycles $A$ and $B$, cycle $C$ may have several vertices in common with $A$ and several (possibly other ones) with $B$. In general there is no way you can consistently apply a 3-coloring. $\endgroup$
    – Leen Droogendijk
    Jun 25, 2014 at 14:59
  • $\begingroup$ Yes I see. Thank you for the clarification. $\endgroup$
    – Cauthon
    Jun 25, 2014 at 15:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .