Take the 2-minute tour ×
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.

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|improve this question

3 Answers 3

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

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

share|improve this answer

Your Answer

 
discard

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.