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

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

CC BY-SA 3.0
2014-01-30T18:01:18.810Z
Check out the [ISGCI entry on perfect graphs](http://www.graphclasses.org/classes/gc_56.html).
Juho
CC BY-SA 3.0
2014-01-30T21:18:32.907Z
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
CC BY-SA 3.0
2014-01-31T20:41:32.883Z
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
<graph-theory>
Super class of perfect graphs
Dibyayan
# Super class of perfect graphs

(Asked by: username_0 on 2014-01-30)

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 ?

**Tags:** graph-theory

> **Comments:**
> **username_1**: Check out the [ISGCI entry on perfect graphs](http://www.graphclasses.org/classes/gc_56.html).  
> **username_2**: 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.  
> **username_3**: 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.  

---

## 0 answers

