Ê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
Théorème des graphes parfaits
Résumé
En mathématiques, et plus précisément en théorie des graphes, le théorème des graphes parfaits (parfois appelé théorème fort des graphes parfaits) est une caractérisation des graphes parfaits par certains sous-graphes , conjecturée par Claude Berge en 1961. Maria Chudnovsky, Neil Robertson, Paul Seymour, et Robin Thomas en annoncèrent la démonstration en 2002, et la publièrent en 2006. Elle valut à leurs auteurs le prix Fulkerson de 2009.
On appelle sous-graphe induit par un certain ensemble de sommets d'un graphe G le graphe formé de ces sommets et des arêtes de G les reliant ; une clique est un sous-graphe induit isomorphe à un graphe complet, c'est-à-dire que tous les sommets sont connectés ; le nombre de clique d'un graphe est le nombre de sommets de sa plus grande clique. Le nombre chromatique d'un graphe est le plus petit nombre de couleurs nécessaire pour qu'il existe une coloration de ce graphe, c'est-à-dire une fonction associant à chaque sommet du graphe une couleur, de telle sorte que deux sommets reliés par une arête aient des couleurs différentes (le nombre chromatique est toujours supérieur ou égal au nombre de clique). Enfin, le graphe complémentaire de G est le graphe ayant les mêmes sommets que G, et dans lequel deux sommets sont reliés si et seulement si ils ne le sont pas dans G.
Avec ces définitions, un graphe parfait est un graphe pour lequel chaque sous-graphe induit a un nombre de clique égal à son nombre chromatique.
De nombreuses classes de graphes sont parfaits, par exemple les graphes bipartis, les graphes cordaux, et les graphes de comparabilité. Dans des travaux de 1961 et 1963 où il définissait pour la première fois ces graphes, Claude Berge remarquait qu'un graphe parfait ne peut contenir de trou impair, c'est-à-dire de graphe induit qui soit un cycle d'ordre impair supérieur à 5, car ceux-ci ont 2 pour nombre de clique et 3 pour nombre chromatique. De même, un graphe parfait ne peut contenir un antitrou impair (c'est-à-dire un trou du graphe complémentaire) car un antitrou de 2k + 1 sommets a k pour nombre de clique et k + 1 pour nombre chromatique (si k > 1).
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.