2
$\begingroup$

I am trying to go about this question by proving the contrapositive: If a graph does not have at least two odd cycles that do not share a vertex, then prove χ(G) < 6 . (χ(G) is the minimum number of colors needed to color the vertices of G where no two adjacent vertices have the same color)

I dont know how to proceed from here. I was thinking of maybe using the fact that graphs without odd cycles are bipartite and therefore 2-colorable.

$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

Hint: Pick the shortest odd cycle $C$, and color all the vertices in $C$. Then color all the other vertices.

(This approach doesn't make sense if there's no odd cycles at all, but you know how to handle that case.)

$\endgroup$
2
  • $\begingroup$ How would I use this to determine if the graph is less than 6-colorable though? $\endgroup$
    – graphtheory
    Commented Dec 3, 2017 at 17:55
  • $\begingroup$ Use only 3 colors for the first step, and only 2 colors for the second step. $\endgroup$
    – Misha Lavrov
    Commented Dec 3, 2017 at 18:00

You must log in to answer this question.

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