A graph is strongly perfect if every induced subgraph has an independent vertex set meeting all maximal cliques
of
(Berge and Duchet 1984, Ravindra 1999).
Every strongly perfect graph is perfect, so any graph that is not perfect cannot be strongly perfect. However, the converse is not necessarily true.
Important classes of strongly perfect graphs include bipartite graphs, comparability graphs, chordal
graphs (also called triangulated graphs), graph
complements of chordal graphs, and -free graphs (i.e., graphs not containing the path
graph
as a vertex-induced subgraph) (Berge and Duchet 1984, Ravindra 1999). In particular,
every cograph is strongly perfect.
Among cycle graphs, is strongly perfect exactly when
or
is even; odd cycles
for
are not strongly perfect since they are not perfect.