Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

If property (P) holds for perfect graphs and almost all graphs does it hold for all graphs?

share|improve this question
6  
Perhaps I misunderstood... How about the property "G is perfect or has at least 20 vertices"? –  Goldstern Sep 21 '12 at 11:31
    
@Goldstern: Obviously this is not the kind of property I had in mind, but you have a good point there. I was thinking of things like Hadwiger's conjecture. –  Felix Goldberg Sep 21 '12 at 12:11
1  
Take one non-perfect graph of each (large enough) order and define the property as being not equal to that chosen graph. You need to work on your question a lot before it makes sense. –  Brendan McKay Sep 21 '12 at 12:53
    
Or then again, take any property which have a finite number of exceptions, each of them a non perfect graph. –  Olivier Sep 21 '12 at 17:30
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.