Graphe trivialement parfait

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 ${\displaystyle T}$ un ensemble partiellement ordonné tel que pour tout ${\displaystyle t\in T}$, l'ensemble ${\displaystyle \{s\in T\mid s<t\}}$ est bien ordonné par la relation <, et aussi tel que ${\displaystyle T}$possède un élément minimum. Alors le graphe de comparabilité de ${\displaystyle T}$ est trivialement parfait, et tout graphe trivialement parfait peut être obtenu de cette manière[8]^,[9].
• Ils sont les graphes qui n'ont pas de sous-graphe induit qui sont le graphe chemin ${\displaystyle P_{4}}$ ni le graphe cycle ${\displaystyle C_{4}}$[10]^,

[11]. Wolk (1962)[3] et Wolk (1965)[5] le prouvent pour les graphes de comparabilité de forêts enracinées.

• Ils sont les graphes dans lesquels chaque sous-graphe induit connexe contient un sommet universel[3].
• Ils sont les graphes qui peuvent être représentés comme les graphes d'intervalles pour un ensemble d'intervalles emboîtés. Un ensemble d'intervalles est emboîtés si deux intervalles quelconques de l'ensemble sont soit disjoints, soit contenus l'un dans l'autre[12].
• Ils sont les graphes qui sont à la fois des cordaux et des cographes[13]. Ceci résulte de la caractérisation des graphes cordaux comme graphes sans cycles induits de longueur supérieure à trois, et des cographes comme les graphes sans chemins induits sur quatre sommets (${\displaystyle P_{4}}$).
• Ils sont les graphes qui sont à la fois des cographes et des graphes d'intervalles[13].
• Ils sont les graphes qui peuvent être formés, à partir de graphes à un sommet, par deux opérations : union disjointe de deux graphes trivialement parfaits ou adjonction d'un nouveau sommet adjacent à tous les sommets d'un graphe trivialement parfait[14]. Ces opérations correspondent, dans la forêt sous-jacente, à former une nouvelle forêt par l'union disjointe de deux forêts d'une part, et à former un arbre en connectant un nouveau nœud racine aux racines de tous les arbres d'une forêt d'autre part.
• Ils sont les graphes dans lesquels, pour chaque arête ${\displaystyle (u,v)}$, les voisinages de ${\displaystyle u}$ et ${\displaystyle v}$ (y compris ${\displaystyle u}$ et ${\displaystyle v}$ eux-mêmes) sont emboîtés : l'un des voisinages est un sous-ensemble de l'autre[15].
• Ils sont les graphes de permutation définis à partir de permutations triables par pile (en)[16]
• Ils sont les graphes qui ont la propriété que dans chacun de leurs sous-graphes induits, le nombre de partitions en cliques est égal au nombre de cliques maximales[17].
• Ils sont les graphes avec la propriété que dans chacun de ses sous-graphes induits le nombre de cliques est égal au nombre pseudo-Grundy[17].
• Ce sont les graphes avec la propriété que dans chacun de ses sous-graphes induits le nombre chromatique est égal au nombre de pseudo-Grundy[17].

Il résulte des caractérisations équivalentes des graphes trivialement parfaits que chaque graphe trivialement parfait est aussi un cographe, un graphe cordal, un graphe ptolémaïque, un graphe d'intervalles et un graphe parfait .

Les graphes à seuil sont exactement les graphes qui sont à la fois eux-mêmes trivialement parfaits et les compléments de graphes trivialement parfaits (graphes co-trivialement parfaits).

Les graphes moulins sont trivialement parfaits.

Frank Pok Man Chu[18] donne un algorithme simple en temps linéaire pour reconnaître les graphes trivialement parfaits, basé sur le parcours LexBFS. Chaque fois que l'algorithme LexBFS retire un sommet v du premier ensemble de sa file d'attente, l'algorithme vérifie que tous les voisins restants de v appartiennent au même ensemble ; si ce n'est pas le cas, un des sous-graphes induits interdits peut être construit à partir de v. Si la vérification réussit pour chaque v, alors le graphe est trivialement parfait. L'algorithme peut aussi être modifié pour tester si un graphe est le complémentaire d'un graphe trivialement parfait, en temps linéaire.

Déterminer si un graphe arbitraires est trivialement parfait après suppression de k arêtes est NP-complet[19] ; le problème est traitable à paramètres fixes[20] et peut être résolu en temps ${\displaystyle O(2.45^{k}(m+n))}$[21].

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Trivially perfect graphs » (voir la liste des auteurs).

• « Trivially perfect graphs », Information System on Graph Classes and their Inclusions

• Portail des mathématiques
• Portail de l'informatique théorique