3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$
3
$\begingroup$

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'$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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