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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$

Your Answer

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