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, but the converse is not necessarily true.

Every P_4-free graph (i.e., every graph not containing the path graph P_4 as a vertex-induced subgraph), is strongly perfect (Ravindra 1999).


See also

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.

Cite this as:

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

Subject classifications