I tried to find a solution to this in the web but couldn't.
Can you tell me if the following sentence is correct or else give me a counterexample?


$G$ is $4$-colorable if and only if each sub-graph $G'$ in $G$ is not isomorphic to $K\_5$.
At first glance it seems to be related to the four color theorem but it is not exactly a planar graph (e.g. $3\times 3$ complete bipartite graph) so it is not identical to FCT. 
Any ideas?



A conjectured criterion for 4-colorable graphs
This is false. In fact, there are graphs that contain no K3's but have arbitrarily high chromatic number.


See this wiki article for one such construction <http://en.wikipedia.org/wiki/Mycielskian>


