graphe parfait

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.
Un graphe G est parfait quand le nombre chromatique de chacun de ses sous-graphes induits est égal à la taille de la plus grande clique comprise dans ce sous-graphe induit.
(Remarque : Un sous-graphe induit est un sous-graphe obtenu en restreignant le graphe à un sous-ensemble de sommets et en conservant toutes les arêtes entre sommets de ce sous-ensemble)
Une définition équivalente d’un graphe parfait est due à Václav Chvátal : « Un graphe est parfait si et seulement si son polytope des stables est défini par les contraintes de clique. »

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, démontré en 1972 par László Lovász : « Un graphe est parfait si et seulement si son complémentaire est parfait ».
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)
Certaines classes de graphes sont des graphes parfaits : les graphes bipartis , les graphes de permutations, les graphes cordaux,
Ces classes de graphes disposent d’application dans des domaines variés.