2

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 ?

Dibyayan
  • 1,016
  • 6
  • 14
  • 6
    Check out the ISGCI entry on perfect graphs. – Juho Jan 30 '14 at 18:01
  • 3
    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 http://cstheory.stackexchange.com/q/2503/109 for other "nice" classes you might find useful. – András Salamon Jan 30 '14 at 21:18
  • 2
    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. – Vinicius dos Santos Jan 31 '14 at 20:41

0 Answers0