Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Graphe parfait
Résumé
En théorie des graphes, le graphe parfait est une notion introduite par Claude Berge en 1960. Il s'agit d'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.
Un graphe est 1-parfait si son nombre chromatique (noté ) est égal à la taille de sa plus grande clique (notée ) : .
Dans ce cas, est parfait si et seulement si tous les sous graphes de sont 1-parfait.
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 croître. Il n'est pas retombé non plus après la publication de la preuve puisque la très grande technicité et la longueur de celle-ci laissent espérer l'existence d'une preuve plus courte et qui en renforce la compréhension.
Les deux principales motivations, en dehors de la théorie des graphes, pour l'étude des graphes parfaits sont d'ordres polyédrique et algorithmique. Ceci tient notamment à l'existence d'une autre définition équivalente d'un graphe parfait due à Václav Chvátal :
Partant de ce résultat, Martin Grötschel, László Lovász et Alexander Schrijver montrent que dans les graphes parfaits on peut résoudre en temps polynomial le problème de la coloration de graphe, équivalant au problème de la recherche du stable maximum et aussi au problème de la recherche de la clique maximum, par le théorème faible.
Théorème des graphes parfaits
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.
Cette conjecture a été démontrée en 1972 par
László Lovász.
Cette conjecture a été démontrée en 2002 par Maria Chudnovsky, Neil Robertson, Paul Seymour et Robin Thomas.
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.
Les graphes suivants sont des graphes parfaits : les graphes bipartis, les line graphs, les graphes de permutations et les graphes cordaux, en particulier les graphes scindés, les graphes ptolémaïques, les graphes à distance héréditaire.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.