# Characterisation of graphs that are not 3-colorable

We know that all graphs with odd cycles (odd number of vertices) are not 2-colorable. Is there a similar characterisation for 3-colorability? I am looking for undirected graphs that are not 3-colorable depending on a single graph property e.g. vertices/edges parity or anything else that can be generalised.

-

As far as we know, there is no simple characterization for 3-colorability. Deciding if a given graph is 3-colorable is $\sf NP$-complete. However, we know plenty of structured graph classes for which the problem is easy. For example, Grötzsch's theorem states every triangle-free planar graph is 3-colorable. Furthermore, such graphs can be 3-colored in linear time. In a random graph setting, almost all graphs with $2.522n$ edges are not 3-colorable [1].

You can find plenty of graph classes for which 3-coloring is easy on ISGCI.

-
does this problem have a relationship to detecting triangles in graphs? there is a lot of research on that & it seems to be a deep/crosscutting question/problem – vzn Mar 26 '14 at 17:40
existence of a triangle ("3-clique") means it cannot be colored with fewer than 3 colors right? – vzn Mar 26 '14 at 17:42

For each value $k\in \mathbb{N}$, any graph that has a $(k+1)$-clique is not $k$-colorable. So a 4-clique rules out the existence of a 3-coloring.

Be aware, that this is only a necessary condition (i.e. there are graphs without a 4-clique that are still not 3-COL), while the odd-length cycle condition for 2-colorings is also sufficient (i.e. any graph without an odd-length cycle is 2-COL).

-
More generally, a graph is 3-colorable if it has no subgraph that requires 4 colors. A 4-clique is just one example. – Austin Buchanan Mar 18 '14 at 16:26

Hajós came up with a calculus for proving that graphs are not 3-colorable. The calculus is complete, in the sense that every non-3-colorable graph can be proved to be non-3-colorable. Pitassi and Urquhart related the strength of this proof system to the classic Extended Frege proof system: if one system is optimal (has short proofs for all true statements), then so is the other.

-