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

  • 6
    $\begingroup$ Perhaps I misunderstood... How about the property "G is perfect or has at least 20 vertices"? $\endgroup$ – Goldstern Sep 21 '12 at 11:31
  • $\begingroup$ @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. $\endgroup$ – Felix Goldberg Sep 21 '12 at 12:11
  • 1
    $\begingroup$ 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. $\endgroup$ – Brendan McKay Sep 21 '12 at 12:53
  • $\begingroup$ Or then again, take any property which have a finite number of exceptions, each of them a non perfect graph. $\endgroup$ – Olivier Sep 21 '12 at 17:30
  • $\begingroup$ Would some sort of monotonicity (upwards or downwards) constraint on your property make this a meaningful question? $\endgroup$ – D. Ror. Oct 19 '16 at 21:31

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.