Graphe trivialement parfait

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[1],[2]. Les graphes trivialement parfaits ont été étudiés pour la première fois par Elliot S. Wolk en 1962[3]; ils ont été nommés ainsi par Golumbic[2] ; Golumbic écrit que « le nom a été choisi car il est trivial de montrer qu'un tel graphique est parfait »[4]. Les graphes trivialement parfaits sont également appelés graphes de comparabilité d'arbres[3],[5], graphes de comparabilité arborescents[6], et graphes à quasi-seuil[7].

Construction d'un graphe trivialement parfait à partir d'intervalles imbriqués et de la relation d'accessibilité dans un arbre.

Caractérisations équivalentes

modifier

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 <, et aussi tel que  possède un élément minimum. Alors le graphe de comparabilité de   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   ni le graphe cycle  [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 ( ).
  • 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  , les voisinages de   et   (y compris   et   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].

Classes de graphes associées

modifier

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.

Reconnaissance

modifier

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  [21].

Notes et références

modifier

Bibliographie

modifier

Lien externe

modifier