TOPICS
Search

Strongly Perfect Graph


A graph is strongly perfect if every induced subgraph H has an independent vertex set meeting all maximal cliques of H (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 P_4-free graphs (i.e., graphs not containing the path graph P_4 as a vertex-induced subgraph) (Berge and Duchet 1984, Ravindra 1999). In particular, every cograph is strongly perfect.

Among cycle graphs, C_n is strongly perfect exactly when n=3 or n is even; odd cycles C_(2k+1) for k>=2 are not strongly perfect since they are not perfect.


See also

Bipartite Graph, Chordal Graph, Cograph, Comparability Graph, Perfect Graph, Weakly Perfect Graph

Explore with Wolfram|Alpha

References

Berge, C. and Duchet, P. "Strongly Perfect Graphs." Ann. Disc. Math. 21, 57-61, 1984.Ravindra, G. "Some Classes of Strongly Perfect Graphs." Disc. Math. 206, 197-203, 1999.Wang, H. Y. "Which Claw-Free Graphs Are Strongly Perfect?" Disc. Math. 306, 2602-2629, 2006.

Referenced on Wolfram|Alpha

Strongly Perfect Graph

Cite this as:

Weisstein, Eric W. "Strongly Perfect Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/StronglyPerfectGraph.html

Subject classifications