A trivially perfect graph is a finite simple graph
such that, for every nonempty induced subgraph
, the independence
number of
equals its number of maximal cliques (Golumbic
1978). Here maximal means maximal under inclusion, rather than necessarily having
maximum size.
Equivalently,
has no induced subgraph isomorphic
to the path graph
or the cycle graph
. Consequently, every trivially perfect graph is a
chordal graph and hence a perfect
graph.