3
$\begingroup$

Chromatic number denoted by $\chi(G)$ of graph $G$ is the minimum number of colours required to properly colour the given graph.

For ODD Cycle chromatic number is 3 and it does not contain triangle as a subgraph. I thought about complete , star, wheel graphs etc, but they don't satisfy the conditions.

I am looking for examples of graphs of $\chi(G)$ $\ge 3$, but does not contain a triangle or odd cycle as subgraph.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

If a graph contains no odd cycle then it is bipartite and so 2-colorable.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.