théorème des graphes parfaits

COMBINATOIRE

La notion de graphe parfait a été introduite par Claude Berge en 1960. Elle est liée à la notion de coloration d’un graphe .
Claude Berge a énoncé des conjectures qui, depuis, ont été démontrées et sont devenues les théorèmes des graphes parfaits :
1 -Le théorème faible, démontré en 1972 par László Lovász : « Un graphe est parfait si et seulement si son complémentaire est parfait ».
2 – Théorème fort, démontré en 2002 et publié en 2006 par Maria Chudnovsky , Neil Robertson, Paul Seymour et Robin Thomas. « 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 ».
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.
Une autre formulation du théorème est : « G est parfait si et seulement si ni G ni son complémentaire ne contiennent de trou de longueur impair ». (Remarque : pour un graphe G simple. Un trou est un cycle sans corde de longueur supérieure à 4).