Graph Theory – Can a Graph be Non 3-Colourable Without $K_4$ as a Subgraph?

Question

As the question asks, is it possible for a graph to have a chromatic number larger than three without it having a 4 vertice complete graph as a sub-graph?

Answer 1

Here's a simple counterexample with 6 vertices. Take a 5-cycle $C_5$. Add a new vertex $A$ and connect it by an edge with each vertex of $C_5$. The resulting graph is not 3-colorable. It it were 3-colorable, then $C_5$ would be 2-colorable, which it isn't.