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.
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
3
As far as we know, there is no simple characterization for 3-colorability. Indeed, deciding if a given graph is 3-colorable is $\sf NP$-complete. Thus, more precisely, there is likely no polynomial-time characterization for 3-colorable graphs.
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.
-
$\begingroup$ 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 $\endgroup$– vznMar 26, 2014 at 17:40
-
$\begingroup$ existence of a triangle ("3-clique") means it cannot be colored with fewer than 3 colors right? $\endgroup$– vznMar 26, 2014 at 17:42
-
$\begingroup$ @vzn Clearly so, i.e., the size of a largest clique is a lower bound for the number of colors needed. But otherwise there is no connection to triangle detection. A graph whose largest clique is of size $\omega$ can still require many more colors (see e.g., Mycielskians). $\endgroup$– JuhoApr 7, 2019 at 16:48
$\begingroup$
$\endgroup$
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.
answered Mar 18, 2014 at 17:48
$\begingroup$
$\endgroup$
1
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).
-
1$\begingroup$ More generally, a graph is 3-colorable if it has no subgraph that requires 4 colors. A 4-clique is just one example. $\endgroup$ Mar 18, 2014 at 16:26