# 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 at 17:40
@vzn At least in a sense that you can find triangles in linear time on planar graphs. Or did you have something else in mind? –  Juho Mar 26 at 17:41
existence of a triangle ("3-clique") means it cannot be colored with fewer than 3 colors right? –  vzn Mar 26 at 17:42
@vzn Yeah, clearly so. The algorithm I'm thinking of for finding triangles (or other small cycles) in planar graphs exploits the fact that the degeneracy of any planar graph is at most 5. –  Juho Mar 26 at 17:51

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 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.

-