Why are they called Trivially Perfect Graphs?

Martin Charles Golumbic

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:

PDF


DOI: 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

 

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