[Solved]: Characterisation of graphs that are not 3-colorable

Problem Detail: 

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.

Asked By : Michael

Answered By : Juho

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.

---

[1] Achlioptas, D., & Molloy, M. (1999). Almost all graphs with 2.522 n edges are not 3-colorable. Electronic Journal of Combinatorics, 6(1), R29.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22754