Graphe trivialement parfait

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 maximalesModèle:,. Les graphes trivialement parfaits ont été étudiés pour la première fois par Elliot S. Wolk en 1962Modèle:Sfnp; 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'arbresModèle:SfnpModèle:,Modèle:Sfnp, graphes de comparabilité arborescents, et graphes à quasi-seuil.

Caractérisations équivalentes

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 $T$ un ensemble partiellement ordonné tel que pour tout $t\in T$, l'ensemble $\{s\in T\mid s<t\}$ est bien ordonné par la relation <, et aussi tel que $T$possède un élément minimum. Alors le graphe de comparabilité de $T$ est trivialement parfait, et tout graphe trivialement parfait peut être obtenu de cette manièreModèle:SfnpModèle:,Modèle:Sfnp.
• Ils sont les graphes qui n'ont pas de sous-graphe induit qui sont le graphe chemin $P_4$ ni le graphe cycle $C_4$Modèle:SfnpModèle:,

Modèle:Sfnp. Wolk (1962)Modèle:Sfnp et Wolk (1965)Modèle:Sfnp 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 universelModèle:Sfnp.
• 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'autreModèle:Sfnp.
• Ils sont les graphes qui sont à la fois des cordaux et des cographes. 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 ($P_4$).
• Ils sont les graphes qui sont à la fois des cographes et des graphes d'intervalles.
• 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. 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 $(u,v)$, les voisinages de $u$ et $v$ (y compris $u$ et $v$ eux-mêmes) sont emboîtés : l'un des voisinages est un sous-ensemble de l'autre.
• Ils sont les graphes de permutation définis à partir de Modèle:LienModèle:Sfnp
• 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 maximalesModèle:Sfnp.
• 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-GrundyModèle:Sfnp.
• 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-GrundyModèle:Sfnp.

Classes de graphes associées

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

Frank Pok Man ChuModèle:Sfnp 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-completModèle:Sfnp ; le problème est traitable à paramètres fixesModèle:Sfnp et peut être résolu en temps $O(2.45^k(m+n))$Modèle:Sfnp.

Bibliographie

• Modèle:Ouvrage Modèle:Inscription nécessaire.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article
• Modèle:Article.
• Modèle:Article
• Modèle:Article Modèle:Accès libre.
• Modèle:Article Modèle:Accès libre.
• Modèle:Article.
• Modèle:Article Modèle:Accès libre.
• Modèle:Article Modèle:Accès libre.
• Modèle:Ouvrage.
• Modèle:Article.

• Modèle:Article Modèle:Accès libre.
• Modèle:Article Modèle:Accès libre.
• Modèle:Article Modèle:Accès libre.

Lien externe

• Modèle:Lien web