Upper Bound on the Chromatic Number of a Graph with No Two Disjoint Odd Cycles

Question

Prove that if a graph does not have two disjoint odd cycles then χ(G) ≤ 5, where χ(G) denotes the minimum number of colors needed to color the vertices of G. χ(G) is the chromatic number of G.

Intuitions:

It is clear that any odd-cycle must have a chromatic number of 3. Each clique of the graph that has an odd-cycle must thus have a chromatic number of three, but I don't see how this helps the proof.

On a related note: would it be easier to prove the contrapositive or use a proof by contradiction?

For self-study.

Answer 1

If $G$ does not contain any odd cycles, then $G$ is bipartite and $\chi (G)\leq 2$. Let $C$ be an odd cycle. Since $G$ does not contain two disjoint odd cycles we know that every odd cycle in $G$ has a common vertex. So $G-C$ contains no odd cycles and it follows that $\chi (G-C) \leq 2$. Since $\chi (C)=3$ we know that $\chi(G)\leq 5$.

Answer 2

I think the easiest way is by construction.

Let $G$ be a graph without two disjoint odd cycles.

If $G$ has no odd cycle, then it's bipartite and 2-colorable.

Otherwise, let $C$ be an odd cycle of $G$. We know $C$ is 3-colorable.

Let $G' = G - V(C)$. Then, $G'$ has no odd cycle, and thus it's bipartite. So $G'$ is 2-colorable.

So it's possible to use 3 colors for the vertices of $C$, plus 2 other colors for the vertices of $G'$.