Théorème des graphes parfaits
Un article de Wikipédia, l'encyclopédie libre.
 |
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).
|
Sommaire |
[modifier] Contexte
Dans le cadre de la théorie des graphes, Claude Berge a introduit en 1960 la notion de graphe parfait comme définissant 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.
[modifier] Théorèmes
Il a proposé deux conjectures de caractérisation de ces graphes parfaits, élevées au rang de théorèmes depuis leur démonstration :
- Théorème faible des graphes parfaits :
- Un graphe est parfait si et seulement si son complémentaire est parfait.
Cette conjecture a été démontrée en 1972 par (en) László Lovász.
- Théorème fort des graphes parfaits :
- 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 D. Seymour et Robin Thomas.
- Remarque
En pratique, on retient et on utilise essentiellement le second théorème. De fait, on parle du « théorème des graphes parfaits » en désignant implicitement le théorème fort.
[modifier] 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 preuve, puisque la très grande technicité et la longueur de celle-ci permet d'espérer l'existence d'une preuve plus courte, renforçant la compréhension. Les deux principales motivations (en dehors de la théorie des graphes) pour l'étude des graphes parfaits sont d'ordre polyèdral et algorithmique. Ceci tient, tout d'abord, à l'existence d'une autre définition équivalente d'un graphe parfait (due à Vasek Chvatal) : 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, un remarquable travail de Lovász et al. montre que l'on peut résoudre en temps polynomial le problème de la coloration, celui du stable maximum (et de la clique maximum aussi par le théorème faible).
[modifier] Références
- Claude Berge, « Graphes et hypergraphes », Dunod, 2e édition, 1973 (en particulier, chapitre 16 sur les graphes parfaits) — ISBN 2-04-016906-7.
- Claude Berge, « Graphes », Gauthier-Villars, 3e édition, 1983 — ISBN 2-04-015555-4.
- László Lovász, « Normal hypergraphs and the perfect graph conjecture », Discrete Math. 2, 253-267, 1972.
- Maria Chudnovsky, Neil Robertson, Paul D. Seymour et Robin Thomas, « Progress on perfect graphs », Math. Programming Ser. B 97, 405-422, 2003 PDF.
