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$

2 Answers 2

4
$\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$
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$
1
  • $\begingroup$ Unfortunately, I believe that your claim of "every odd cycle in $G$ has a common vertex" is false. As a counter example, take a triangle with it's midpoints, and connect up the midpoints. So we have 6 vertices with 9 edges. Then, any 2 cycles will intersect in at one of the midpoints, but the 3 outer triangles do not have a common vertex. $\endgroup$
    – Calvin Lin
    Commented Apr 30 at 1:03

You must log in to answer this question.

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