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

Caractérisations équivalentes[modifier | modifier le code]

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ère^[8]^,^[9].
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}$ ^[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 ( $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 $(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^[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 | modifier le code]

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 | modifier le code]

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 $O(2.45^{k}(m+n))$ ^[21].

Notes et références[modifier | modifier le code]

(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).

↑ Brandstädt, Le et Spinrad 1999, définition 2.6.2, p.34
↑ ^{a et b} Golumbic 1978.
↑ ^{a b c et d} Wolk (1962).
↑ « the name was chosen since it is trivial to show that such a graph is perfect . »
↑ ^{a et b} Wolk (1965).
↑ Donnelly et Isaak 1999.
↑ Yan, Chen et Chang 1996.
↑ Brandstädt, Le et Spinrad (1999), Theorem 6.6.1, p. 99.
↑ Golumbic (1978), Corollary 4.
↑ Brandstädt, Le et Spinrad (1999), theorem 6.6.1, p. 99.
↑ Golumbic (1978), theorem 2.
↑ Brandstädt, Le et Spinrad (1999), p. 51.
↑ ^{a et b} Brandstädt, Le et Spinrad 1999, p. 248 ; Yan, Chen et Chang 1996, theorem 3.
↑ Yan, Chen et Chang 1996 ; Gurski 2006.
↑ Yan, Chen et Chang 1996, theorem 3.
↑ Rotem (1981).
↑ ^{a b et c} Rubio-Montiel (2015).
↑ Chu (2008).
↑ Sharan (2002).
↑ Cai (1996).
↑ Nastos et Gao (2010).

Bibliographie[modifier | modifier le code]

Andreas Brandstädt, Van Bang Le et Jeremy Spinrad, Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, 1999 (ISBN 0-89871-432-X, lire en ligne) .
Leizhen Cai, « Fixed-parameter tractability of graph modification problems for hereditary properties », Information Processing Letters, vol. 58, n^o 4,‎ 1996, p. 171–176 (DOI 10.1016/0020-0190(96)00050-6).
Frank Pok Man Chu, « A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements », Information Processing Letters, vol. 107, n^o 1,‎ 2008, p. 7–12 (DOI 10.1016/j.ipl.2007.12.009).
Sam Donnelly et Garth Isaak, « Hamiltonian powers in threshold and arborescent comparability graphs », Discrete Mathematics, vol. 202, n^os 1-3,‎ 1999, p. 33–44 (DOI 10.1016/S0012-365X(98)00346-X)
Laurent Feuilloley et Michel Habib, « Graph Classes and Forbidden Patterns on Three Vertices », SIAM Journal on Discrete Mathematics, vol. 35, n^o 1,‎ 2021, p. 55–90 (DOI 10.1137/19M1280399, arXiv 1812.05913).
G. R. Gandal et R. Mary Jeya Jothi, « Some classes of Trivially Perfect Graphs », Journal of Physics: Conference Series, vol. 1770, n^o 1,‎ 2021, p. 012074 (ISSN 1742-6588, DOI 10.1088/1742-6596/1770/1/012074)
Martin Charles Golumbic, « Trivially perfect graphs », Discrete Mathematics, vol. 24, n^o 1,‎ 1978, p. 105–107 (DOI 10.1016/0012-365X(78)90178-4) .
Frank Gurski, « Characterizations for co-graphs defined by restricted NLC-width or clique-width operations », Discrete Mathematics, vol. 306, n^o 2,‎ 2006, p. 271–277 (DOI 10.1016/j.disc.2005.11.014) .
James Nastos et Yong Gao, « A Novel Branching Strategy for Parameterized Graph Modification Problems », Lecture Notes in Computer Science, vol. 6509,‎ 2010, p. 332–346 (arXiv 1006.3020).
Doron Rotem, « Stack sortable permutations », Discrete Mathematics, vol. 33, n^o 2,‎ 1981, p. 185–196 (DOI 10.1016/0012-365X(81)90165-5, MR 599081) .
Christian Rubio-Montiel, « A new characterization of trivially perfect graphs », Electronic Journal of Graph Theory and Applications, vol. 3, n^o 1,‎ 2015, p. 22–26 (DOI 10.5614/ejgta.2015.3.1.3, lire en ligne) .
Roded Sharan (Thèse Ph.D.), Graph modification problems and their applications to genomic research, Université de Tel Aviv, 2002.
Shuhei Tsujie, « The Chromatic Symmetric Functions of Trivially Perfect Graphs and Cographs », Graphs and Combinatorics, vol. 34,‎ 2018, p. 1037-1048 (DOI 10.1007/s00373-018-1928-2, arXiv 1707.04058).

Elliot S. Wolk, « The comparability graph of a tree », Proceedings of the American Mathematical Society, vol. 13,‎ 1962, p. 789–795 (DOI 10.1090/S0002-9939-1962-0172273-0) .
Elliot S. Wolk, « A note on the comparability graph of a tree », Proceedings of the American Mathematical Society, vol. 16,‎ 1965, p. 17–20 (DOI 10.1090/S0002-9939-1965-0172274-5) .
Jing-Ho Yan, Jer-Jeong Chen et Gerard J. Chang, « Quasi-threshold graphs », Discrete Applied Mathematics, vol. 69, n^o 3,‎ 1996, p. 247–255 (DOI 10.1016/0166-218X(96)00094-7) .

Lien externe[modifier | modifier le code]

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

[1] Brandstädt, Le et Spinrad 1999, définition 2.6.2, p.34

[Golumbic-2] {a et b} Golumbic 1978.

[Wolk1962-3] {a b c et d} Wolk (1962).

[4] « the name was chosen since it is trivial to show that such a graph is perfect . »

[Wolk1965-5] {a et b} Wolk (1965).

[6] Donnelly et Isaak 1999.

[7] Yan, Chen et Chang 1996.

[BrandstädtLeSpinrad1999Theorem_6.6.1,_p._99-8] Brandstädt, Le et Spinrad (1999), Theorem 6.6.1, p. 99.

[Golumbic1978Corollary_4-9] Golumbic (1978), Corollary 4.

[BrandstädtLeSpinrad1999theorem_6.6.1,_p._99-10] Brandstädt, Le et Spinrad (1999), theorem 6.6.1, p. 99.

[Golumbic1978theorem_2-11] Golumbic (1978), theorem 2.

[BrandstädtLeSpinrad199951-12] Brandstädt, Le et Spinrad (1999), p. 51.

[intersect-13] {a et b} Brandstädt, Le et Spinrad 1999, p. 248 ; Yan, Chen et Chang 1996, theorem 3.

[14] Yan, Chen et Chang 1996 ; Gurski 2006.

[15] Yan, Chen et Chang 1996, theorem 3.

[Rotem1981-16] Rotem (1981).

[Rubio-Montiel2015-17] {a b et c} Rubio-Montiel (2015).

[Chu2008-18] Chu (2008).

[Sharan2002-19] Sharan (2002).

[Cai1996-20] Cai (1996).

[NastosGao2010-21] Nastos et Gao (2010).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]