Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 6 down vote accepted

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.

share|cite|improve this answer
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).

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.