Graphe trivialement parfait

vignette|upright=2| Construction d'un graphe trivialement parfait à partir d'intervalles imbriqués et de la relation d'accessibilité dans un arbre. En théorie des graphes, un graphe trivialement parfait est un graphe qui a la propriété que dans chacun de ses sous-graphes induits, la taille du stable maximal est égale au nombre de cliques maximales. Les graphes trivialement parfaits ont été étudiés pour la première fois par Elliot S. Wolk en 1962; ils ont été nommés ainsi par Golumbic ; Golumbic écrit que « le nom a été choisi car il est trivial de montrer qu'un tel graphique est parfait ». Les graphes trivialement parfaits sont également appelés graphes de comparabilité d'arbres, graphes de comparabilité arborescents, et graphes à quasi-seuil. Les graphes trivialement parfaits ont plusieurs autres caractérisations équivalentes : Ils sont les graphes des arbres de comparabilité des arbres de la théorie des ordres. Autrement dit, soit un ensemble partiellement ordonné tel que pour tout , l'ensemble est bien ordonné par la relation