Théorème des graphes parfaits
Un article de Wikipédia, l'encyclopédie libre.
 |
Cet article est une ébauche à compléter concernant les mathématiques, vous pouvez partager vos connaissances en le modifiant. |
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] Références
- Claude Berge, « Graphes et hypergraphes », Dunod, 2ème édition, 1973 (en particulier, chapitre 16 sur les graphes parfaits) — ISBN 2040169067.
- Claude Berge, « Graphes », Gauthier-Villars, 3ème édition, 1983 — ISBN 2040155554.
- 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.
[modifier] Liens internes
|
Portail des mathématiques – Accédez aux articles de Wikipédia concernant les mathématiques. |
