Can a graph be non 3-colourable without having k4 as a sub graph? 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?

A non-constructive counter-example comes from a theorem of Erdős: For any $\chi$ and $g$, there exists graphs of chromatic number at least $\chi$ and girth at least $g$. If we pick $g=\chi = 4$ then there exists a graph which is not $3$-colourable and is triangle free and therefore cannot possible contain a $K_4$ sub-graph.
