Perfect graphs exhibits many nice properties which enables NP complete problems to be solvable in polynomial time.

My question: Are there any result which indicates existence of some superclass of perfect graphs with similar properties ?

  • 6
    $\begingroup$ Check out the ISGCI entry on perfect graphs. $\endgroup$
    – Juho
    Commented Jan 30, 2014 at 18:01
  • 3
    $\begingroup$ As far as I know, no such results are known. Some "nice-ish" superclasses do exist, such as normal graphs, but the best hope may be related classes such as b-perfect graphs, which are not superclasses. See also cstheory.stackexchange.com/q/2503/109 for other "nice" classes you might find useful. $\endgroup$ Commented Jan 30, 2014 at 21:18
  • 2
    $\begingroup$ Although some NP-complete problems such as coloring can be solved in polynomial time for perfect graphs, there are many other problems that are still NP-complete even for very restricted subclasses of it. Every graph class has properties that help solving a particular problem. It depends a lot on the structures of the problem and of the class. I think a proper answer would depend on the problem you are considering. $\endgroup$ Commented Jan 31, 2014 at 20:41


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.