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.