patternMinor
Characterisation of graphs that are not 3-colorable
Viewed 0 times
aregraphscolorablecharacterisationthatnot
Problem
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.
Solution
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.
[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.
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.
Context
StackExchange Computer Science Q#22754, answer score: 9
Revisions (0)
No revisions yet.