[Math] edges in at most one odd cycle, 3 colorable

coloringgraph theory

Prove that if $G$ is a graph in which every edge is a part of at most one odd length cycle, then the graph is 3 colorable.

I want to show that if a graph is 4-critical there are two odd cycles which share an edge, which would prove the question. I'm not sure how to get that. I thought to take a maximum path, and then an end point has at least 3 neighbours in the path, which ensures 3 cycles, but I don't see a reason they can't all be even.

Best Answer

Here are some hints that lead to a proof.

Show that a 2-connected graph in which every edge is on at most one odd cycle is either bipartite or an odd cycle (e.g. by using an ear decomposition).

Show that the chromatic number of a graph equals the maximum of the chromatic numbers of its blocks.

As an alternative for the second part: use induction on the number of vertices. If $G$ is 2-connected we proved it in the first part. Otherwise $G$ has a cut vertex $v$. For a component $C$ of $G-v$ show that the conditions of the problem hold in $C+v$ (since cycles must be contained completely in one such enhanced component). So you can use the induction hypothesis on each such component ($+v$) and glue them together (you can always make sure that $v$ has color 1 in each of them).