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 ?
$\begingroup$
$\endgroup$
3
-
6$\begingroup$ Check out the ISGCI entry on perfect graphs. $\endgroup$– JuhoJan 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$– András SalamonJan 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$– Vinicius dos SantosJan 31, 2014 at 20:41
Add a comment
|