TOPICS
Search

Trivially Perfect Graph


A trivially perfect graph is a finite simple graph G such that, for every nonempty induced subgraph H, the independence number of H equals its number of maximal cliques (Golumbic 1978). Here maximal means maximal under inclusion, rather than necessarily having maximum size.

Equivalently, G has no induced subgraph isomorphic to the path graph P_4 or the cycle graph C_4. Consequently, every trivially perfect graph is a chordal graph and hence a perfect graph.


See also

Chordal Graph, Perfect Graph

Explore with Wolfram|Alpha

References

Golumbic, M. C. "Trivially Perfect Graphs." Disc. Math. 24, 105-107, 1978. https://doi.org/10.1016/0012-365X(78)90178-4.

Cite this as:

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

Subject classifications