théorème des graphes parfaits

Colorier un graphe consiste à donner une couleur à chaque sommet sans attribuer la même couleur à deux sommets reliés. Une clique est un groupe de sommets tous reliés deux à deux : chacun d'eux doit donc recevoir une couleur différente. La taille de la plus grande clique fournit ainsi un minimum de couleurs nécessaires.

Dans un graphe parfait, ce minimum suffit toujours, même après avoir gardé n'importe quel choix de sommets avec toutes les arêtes qui les relient. Le théorème fort de 2002 traduit cette propriété globale en un obstacle précis : les cycles impairs sans raccourci d'au moins cinq sommets, dans le graphe ou dans son complémentaire.

Soit G un graphe simple fini. Pour tout sous-graphe induit H de G, le nombre chromatique χ(H) est le plus petit nombre de couleurs d'une coloration propre de ses sommets, et le nombre de clique ω(H) est le nombre de sommets d'une plus grande clique de H. Comme les sommets d'une clique doivent porter des couleurs distinctes, ω(H) ≤ χ(H).

Le graphe G est parfait lorsque χ(H) = ω(H) pour chaque sous-graphe induit H, y compris G lui-même. Le complémentaire de G, noté G̅, conserve les mêmes sommets et relie exactement les paires distinctes qui ne sont pas reliées dans G. Dans la formulation du théorème, un trou est un cycle induit de longueur au moins 4 ; lorsqu'il est impair, sa longueur est donc au moins égale à 5. Son complémentaire est appelé antitrou. Claude Berge a introduit la notion de graphe parfait en 1960 et formulé les deux conjectures devenues les théorèmes faible et fort.

Le théorème fort des graphes parfaits affirme qu'un graphe simple fini G est parfait si et seulement si G ne contient ni trou impair ni antitrou impair. Autrement dit, ni G ni son complémentaire G̅ ne doivent contenir de cycle induit de longueur impaire au moins égale à 5.

Le théorème faible des graphes parfaits, démontré auparavant par Lovász, affirme que G est parfait si et seulement si G̅ est parfait. Il découle du théorème fort, car les trous impairs et les antitrous impairs s'échangent lorsqu'on prend le complémentaire.

La formulation standard porte sur un graphe simple fini non orienté : il n'a ni boucle ni arêtes multiples, et son ensemble de sommets est fini. La perfection et les cycles interdits s'examinent dans les sous-graphes induits, obtenus en choisissant des sommets puis en conservant toutes les arêtes de G entre eux.

Le cycle interdit doit être impair, comporter au moins cinq sommets et être sans corde, c'est-à-dire sans arête reliant deux sommets non consécutifs du cycle. La recherche doit être faite dans G et dans G̅ ; examiner seulement le graphe initial ne suffit pas.

Considérons le cycle C₅ formé par cinq sommets A, B, C, D et E, avec pour seules arêtes AB, BC, CD, DE et EA. Le schéma montre ce pentagone sans corde et met en regard la coloration et la taille des cliques.

1. Toute clique de C₅ contient au plus deux sommets : trois sommets ne sont jamais tous adjacents deux à deux. Une arête forme bien une clique de taille 2, donc ω(C₅) = 2.

2. Deux couleurs ne suffisent pas. En alternant les couleurs le long de A–B–C–D–E, les sommets A et E reçoivent la même couleur alors qu'ils sont adjacents. Une troisième couleur permet de terminer la coloration, donc χ(C₅) = 3.

3. L'inégalité χ(C₅) ≠ ω(C₅) montre déjà que C₅ n'est pas parfait.

4. Les cinq sommets forment un cycle induit impair sans corde. C₅ est donc exactement un trou impair interdit par le théorème fort, qui aboutit au même diagnostic. Son complémentaire est lui aussi un cycle à cinq sommets.

Pour montrer qu'un graphe n'est pas parfait, un seul certificat suffit : un sous-graphe induit H pour lequel χ(H) > ω(H), ou un trou impair dans G ou dans G̅. Le cycle à cinq sommets en fournit l'exemple minimal.

Pour établir la perfection, vérifier seulement χ(G) = ω(G) ne suffit pas : tous les sous-graphes induits comptent. La caractérisation forte remplace cette famille d'égalités par l'absence de trous et d'antitrous impairs.

Cette structure a aussi une portée algorithmique. Sur les graphes parfaits, des algorithmes spécialisés permettent de résoudre en temps polynomial des problèmes comme la coloration optimale, la clique maximum et l'ensemble stable maximum, qui sont difficiles sur les graphes généraux.

Un graphe parfait n'est pas un graphe complet. Dans un graphe complet, tous les sommets sont adjacents ; la famille des graphes parfaits est beaucoup plus large et comprend notamment les graphes bipartis.

Le théorème des graphes parfaits désigne usuellement la caractérisation forte par les trous et antitrous impairs. Le théorème faible concerne uniquement la conservation de la perfection par passage au graphe complémentaire.

Un nombre parfait appartient à l'arithmétique et égale la somme de ses diviseurs propres. L'adjectif « parfait » est commun, mais cette notion n'a aucun lien avec l'égalité entre nombre chromatique et nombre de clique.

L'égalité sur G seul est insuffisante. Un graphe peut satisfaire χ(G) = ω(G) tout en possédant un sous-graphe induit H qui ne la satisfait pas. La perfection est une propriété héréditaire par sous-graphe induit.

Une corde supprime l'obstruction observée. Un cycle impair d'au moins cinq sommets n'est un trou que s'il est induit. Si une corde relie deux sommets non consécutifs, ce cycle précis ne constitue pas le certificat interdit, même si un autre trou impair peut subsister dans le graphe.

Les triangles ne sont pas interdits. Un cycle de longueur 3 est une clique : son nombre chromatique et son nombre de clique valent tous deux 3. L'interdiction commence à la longueur 5.

Le complémentaire ne peut pas être omis. Un graphe sans trou impair peut encore contenir un antitrou impair, c'est-à-dire un trou impair dans son complémentaire. La formulation symétrique est indispensable, sauf pour C₅, qui est isomorphe à son propre complémentaire.

La fiche graphe parfait approfondit la propriété χ(H) = ω(H) et les principales familles qui la satisfont.

La fiche nombre chromatique d'un graphe détaille le minimum de couleurs comparé au nombre de clique dans la définition de la perfection.

La fiche clique d'un graphe précise la structure complète dont la taille fournit la borne inférieure ω(H).