Graphe parfait

En théorie des graphes, le graphe parfait est une notion introduite par Claude Berge en 1960. Il s'agit d'un graphe pour lequel le nombre chromatique de chaque sous-graphe induit et la taille de la plus grande clique dudit sous-graphe induit sont égaux.

Graphe parfait avec une clique de trois sommets.

Un graphe $G$ est 1-parfait[1] si son nombre chromatique (noté $\chi (G)$ ) est égale à la taille de sa plus grande clique (notée $\omega (G)$ ) : $\chi (G)=\omega (G)$ . Dans ce cas, $G$ est parfait si et seulement si tous les sous graphes de $G$ sont 1-parfait.

Intérêt

Depuis la formulation des conjectures jusqu'à la démonstration du théorème fort, l'intérêt pour les graphes parfaits n'a cessé de croitre. Il n'est pas retombé non plus après la publication de la preuve puisque la très grande technicité et la longueur de celle-ci laissent espérer l'existence d'une preuve plus courte et qui en renforce la compréhension.

Les deux principales motivations, en dehors de la théorie des graphes, pour l'étude des graphes parfaits sont d'ordres polyédrique et algorithmique. Ceci tient notamment à l'existence d'une autre définition équivalente d'un graphe parfait due à Václav Chvátal[2] :

« Un graphe est parfait si et seulement si son polytope des stables est défini par les contraintes de clique. »

Partant de ce résultat, Martin Grötschel, László Lovász et Alexander Schrijver montrent que dans les graphes parfaits on peut résoudre en temps polynomial le problème de la coloration de graphe[3], équivalant au problème de la recherche du stable maximum et aussi au problème de la recherche de la clique maximum, par le théorème faible.

Théorèmes

Claude Berge a émis deux conjectures caractérisant ces graphes parfaits. Elles ont été démontrées en 1972 et 2002 et sont devenues des théorèmes.

Théorème faible des graphes parfaits

Théorème — Un graphe est parfait si et seulement si son complémentaire est parfait.

Cette conjecture a été démontrée en 1972 par László Lovász[4].

Théorème fort des graphes parfaits

Théorème — Un graphe est parfait si et seulement si ni lui ni son complémentaire ne contiennent de cycle impair induit de longueur au moins cinq

Cette conjecture a été démontrée en 2002 par Maria Chudnovsky, Neil Robertson, Paul Seymour et Robin Thomas.

Remarque

Le théorème fort implique trivialement le théorème faible. De fait on parle du « théorème des graphes parfaits » en désignant implicitement le théorème fort.

Classes de graphes parfaits

Les graphes suivants sont des graphes parfaits : les graphes bipartis, les line graphs, les graphes de permutations et les graphes cordaux, en particulier les graphes scindés, les graphes ptolémaïques, les graphes à distance héréditaire.

Notes et références

Coudert, Olivier (1997). « Exact Coloring of Real-Life Graphs is Easy » : 121–12 p., DAC '97: Proceedings of the 34th annual Design Automation Conference (DOI:10.1145/266021.266047).
(en) Václav Chvátal, « On certain polytopes associated with graphs », JCTB, vol. 18,‎ 1975, p. 138-154.
(en) Martin Grötschel, László Lovász et Alexander Schrijver, Geometric algorithms and combinatorial optimization, Springer, 1988, 362 p. (ISBN 0-387-13624-X) et (2^e éd. corrigée, 1993) (ISBN 978-0-387-56740-2).
(en) László Lovász, « Normal hypergraphs and the perfect graph conjecture », Discrete Math., vol. 2, n^o 3,‎ 1972, p. 253-267 (DOI 10.1016/0012-365X(72)90006-4).

Voir aussi

Bibliographie

Claude Berge, Graphes et hypergraphes, Dunod, 2^e éd., 1973 (ISBN 2-04-016906-7) (en particulier, chapitre 16 sur les graphes parfaits)
Claude Berge, Graphes, Gauthier-Villars, 3^e éd., 1983 (ISBN 2-04-015555-4)
(en) Maria Chudnovsky, Neil Robertson, Paul D. Seymour et Robin Thomas, « Progress on perfect graphs », dans Math. Programming Ser. B, vol. 97, 2003, p. 405-422, PDF

Articles connexes

Lien externe

Natalie Wolchover, « Theorists Draw Closer to Perfect Coloring », sur QuantaMagazine, 20 octobre 2015

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

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[1] Coudert, Olivier (1997). « Exact Coloring of Real-Life Graphs is Easy » : 121–12 p., DAC '97: Proceedings of the 34th annual Design Automation Conference (DOI:10.1145/266021.266047).

[2] (en) Václav Chvátal, « On certain polytopes associated with graphs », JCTB, vol. 18,‎ 1975, p. 138-154.

[3] (en) Martin Grötschel, László Lovász et Alexander Schrijver, Geometric algorithms and combinatorial optimization, Springer, 1988, 362 p. (ISBN 0-387-13624-X) et (2^e éd. corrigée, 1993) (ISBN 978-0-387-56740-2).

[4] (en) László Lovász, « Normal hypergraphs and the perfect graph conjecture », Discrete Math., vol. 2, n^o 3,‎ 1972, p. 253-267 (DOI 10.1016/0012-365X(72)90006-4).