Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
4  
1  
Thanks! Yes, that's probably it. (How to accept a comment?) –  Anonymous Sep 5 '12 at 15:26
    
You can't, but I added it as an answer. Sorry I can't explicate more but I'm barely familiar with this subject. –  Dan Brumleve Sep 23 '12 at 8:49

1 Answer 1

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

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.