graphe parfait

Imaginez quatre points reliés en chaîne : A–B–C–D. Deux couleurs suffisent pour colorier les points en alternance, et deux points voisins forment la plus grande clique. Les deux nombres valent donc 2. Un graphe est parfait lorsque cet accord ne se produit pas seulement pour le dessin entier, mais reste vrai chaque fois que l’on conserve n’importe quel groupe de sommets avec toutes les arêtes qui les reliaient déjà.

Soit un graphe G. Pour chaque sous-ensemble de ses sommets, le sous-graphe induit H conserve exactement les arêtes de G dont les deux extrémités appartiennent à ce sous-ensemble. Le nombre chromatique de H, noté χ(H), est le minimum de couleurs permettant de colorier ses sommets sans donner la même couleur à deux voisins. La taille maximale d’une clique de H, notée ω(H), est le nombre de sommets de sa plus grande clique, c’est-à-dire de son plus grand ensemble de sommets deux à deux adjacents.

Le graphe G est parfait lorsque l’égalité suivante vaut pour tout sous-graphe induit H :

L’inégalité χ(H) ≥ ω(H) vaut toujours, car les sommets d’une clique exigent tous des couleurs différentes. La perfection affirme que cette borne suffit toujours, y compris après suppression de sommets. Le théorème faible, démontré par László Lovász en 1972, ajoute que G est parfait si et seulement si son graphe complémentaire l’est. Le théorème fort, démontré en 2002 puis publié en 2006 par Maria Chudnovsky, Neil Robertson, Paul Seymour et Robin Thomas, donne un critère équivalent : ni G ni son complémentaire ne doivent contenir de cycle induit sans corde, de longueur impaire au moins égale à 5.

La propriété articule cinq éléments. Le graphe G fournit les sommets et les arêtes. Un choix de sommets détermine un sous-graphe induit H : on garde toutes les arêtes de G entre les sommets choisis, sans pouvoir en retirer à volonté. Une coloration de H répartit ses sommets en couleurs, avec des couleurs différentes aux extrémités de chaque arête. Son minimum donne χ(H). Une clique de H rassemble des sommets tous reliés deux à deux ; sa taille maximale donne ω(H).

Les arêtes imposent donc à la fois les incompatibilités de couleur et les cliques candidates. La perfection dépend de l’égalité entre les deux optimums pour chaque choix de sommets, pas de la position des points, de la longueur des traits ni des couleurs du dessin. Ces données suffisent à tester un petit graphe en examinant ses sous-graphes induits, ou à chercher l’obstruction donnée par le théorème fort.

Considérons le chemin à quatre sommets A–B–C–D. La figure montre une coloration optimale en deux couleurs et met en évidence l’arête B–C, qui est une clique maximale.

Données.
Sommets : A, B, C et D.
Arêtes : A–B, B–C et C–D.
Couleurs : jaune pour A et C, rouge pour B et D.

Étape 1. Une seule couleur ne convient pas, puisque A et B sont voisins. L’alternance jaune–rouge–jaune–rouge convient, donc le nombre chromatique du chemin vaut 2.

Étape 2. Chaque arête, notamment B–C, forme une clique de taille 2. Aucun triangle n’existe dans ce chemin, donc sa plus grande clique a exactement 2 sommets. Les deux optimums sont égaux.

Étape 3. Prenons maintenant un sous-graphe induit non vide. S’il contient une arête, il a besoin de deux couleurs et possède une clique de taille 2. S’il ne contient aucune arête, une couleur suffit et sa plus grande clique a taille 1.

Contrôle. Tous les sous-graphes induits non vides vérifient ainsi l’égalité entre nombre chromatique et taille de clique maximale. Le chemin A–B–C–D est donc parfait.

Pour résoudre une coloration sur un graphe reconnu parfait, on cherche d’abord une clique maximum, de taille ω(G). Sa taille donne à la fois une borne nécessaire et le nombre exact de couleurs de la coloration optimale. Sur un graphe quelconque, cette taille ne fournit qu’une borne inférieure.

Pour reconnaître la propriété, le théorème fort remplace l’examen direct de tous les sous-graphes induits par la recherche d’un trou impair dans le graphe ou son complémentaire. La découverte d’un tel cycle suffit à conclure que le graphe n’est pas parfait.

Lorsque le graphe appartient déjà à une classe citée comme parfaite — graphe biparti, graphe de permutations ou graphe cordal — cette appartenance établit la propriété. Si la classe n’est pas connue, il faut revenir à la définition ou au critère d’obstruction.

Graphe parfait et graphe complet. Dans un graphe complet, tous les sommets sont voisins deux à deux. Un graphe parfait n’a pas besoin d’être complet : le chemin A–B–C–D est parfait, alors que A et C ne sont pas voisins.

Perfection et égalité sur le graphe entier. Constater χ(G) = ω(G) ne suffit pas. Le critère doit rester vrai pour chaque sous-graphe induit H ; un seul sous-graphe induit qui échoue rend G non parfait.

Graphe parfait et graphe biparti. Tout graphe biparti appartient aux classes parfaites citées, mais la réciproque est fausse. Un triangle est parfait, puisqu’il est complet, mais il n’est pas biparti.

Oublier le mot « induit ». Retirer arbitrairement une arête ne produit pas le sous-graphe demandé par la définition. Il faut choisir des sommets, puis conserver toutes les arêtes du graphe initial entre eux.

Repérer n’importe quel cycle impair. L’obstruction du théorème fort est un cycle impair sans corde, induit, de longueur au moins 5. Un triangle ne bloque pas la perfection ; un cycle de longueur 5 muni d’une corde n’est pas non plus un trou induit.

N’examiner que le graphe. L’absence de trou impair dans G ne suffit pas : son complémentaire doit également en être dépourvu. Le critère symétrique porte sur les deux graphes.

Réduire la formulation polyédrale aux seules inégalités supérieures. Dans un graphe parfait, les contraintes de clique décrivent le polytope des stables avec les contraintes de non-négativité des variables. Pour un graphe général, ces contraintes ne donnent qu’une relaxation. Omettre la non-négativité laisserait en outre entrer des points qui ne représentent aucun stable.

coloration d'un graphe — Pour approfondir le nombre chromatique et la règle qui interdit une même couleur à deux sommets adjacents.

clique - graphe - — Pour étudier les sous-graphes complets dont la taille fournit la borne centrale de la perfection.

graphe biparti — Pour retrouver une classe entière de graphes parfaits à travers une structure en deux ensembles de sommets.