Why are they called Trivially Perfect Graphs?
Resumo
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:
PDFDOI: https://doi.org/10.12957/cadinf.2022.70585
Apontamentos
- Não há apontamentos.
ISSN: 1413-9014 / E-ISSN: 2317-2193
DOI: dx.doi.org/10.12957/cadinf
This work is licensed under a Creative Commons Attribution 4.0 International License