Why are they called Trivially Perfect Graphs?

Martin Charles Golumbic


Trivially perfect graphs are graphs for which the stability number equals the number of (maximal) cliques, for every induced subgraph. Trivially perfect graphs are equivalent to the {C_4, P_4}-free graphs, and to the comparability graphs orders whose Hasse diagram is a rooted tree. We survey classical and recent results on this fascinating and highly non-trivial graph family.

Texto completo:


DOI: https://doi.org/10.12957/cadinf.2022.70585


  • Não há apontamentos.


ISSN: 1413-9014 / E-ISSN: 2317-2193

DOI: dx.doi.org/10.12957/cadinf


Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License