Graphe cordal - Définition
La liste des auteurs de cet article est disponible ici.
Relation avec les autres classes de graphe
Sous-classes
Les graphes d'intervalle sont les graphes d'intersection de sous-arbres de graphes chemin; ainsi, ils sont une sous-famille des graphes cordaux.
Les graphes fendus sont exactement les graphes à la fois cordaux et complémentaires de graphes cordaux. Bender et al. (1985) ont montré, en notant F(n) le nombre de graphes fendus à n sommets et C(n) le nombre de graphes cordaux à n sommets, que F(n) / C(n) tendait vers 1 lorsque n tendait vers l'infini.
Les graphes de quasi-seuil sont exactement les graphes qui sont à la fois cordaux et cographes.
Sur-classes
Les graphes cordaux sont une sous-classe des graphes sans trou pair et des graphes graphes sans trou impair, puisque les graphes cordaux sont par définition les graphes sans trou (un trou étant un cycle de longueur au moins 4).
