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 Jan 30 '14 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$ – András Salamon Jan 30 '14 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$ – Vinicius dos Santos Jan 31 '14 at 20:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.