1
$\begingroup$

Recently I heard someone talking about a general result saying that a graph property satisfying certain conditions always is characterizable via a (finite) set of 'smallest examples' (similar to the famous characterization of non-planar graphs as those that contain either the complete 5-graph or the 3-3 graph).

Does anyone recognize what I'm talking about? Where can I find more details on this?

  • 0
    You ca$n$'t, but I added it as an answer. Sorry I can't explicate more but I'm barely familiar with this subject.2012-09-23

1 Answers 1

3

You must be looking for the Robertson-Seymour theorem which generalizes Kuratowski's planar graph theorem.