GRAPHES PARFAITS THÉORÈME FORT DES

Vous organisez un colloque dans lequel plusieurs conférences sont données simultanément (dans des salles différentes et à des horaires imposés par les orateurs) et vous cherchez à occuper le moins de salles possibles (car vous devez les louer). Une méthode permettant de réaliser un tel planning consiste à construire un graphe G dans lequel les conférences seront représentées par des sommets tandis que le fait que deux conférences se tiennent, au moins en partie, en même temps sera symbolisé par une arête reliant les deux sommets associés.

On cherche à affecter une salle (repérée par un numéro) à chaque conférence, de telle sorte que deux conférences adjacentes (reliées par une arête) ne soient pas dans la même salle. Une telle affectation est appelée une coloration et le nombre de couleurs est au moins égal au plus grand nombre W(G) de sommets de G deux à deux adjacents. Par exemple, un cycle (graphe dont les sommets sont reliés uniquement à leur prédécesseur et leur successeur) est coloriable en 2 (nombre pair de sommets) ou 3 (nombre impair de sommets) couleurs.

Le graphe précédent est un graphe d'intervalle et fait partie de la famille des graphes parfaits introduite par le Français Claude Berge (1926-2002) au début des années 1960. Ces graphes sont ceux pour lesquels tout sous-graphe induit H (défini par des sommets et toutes les arêtes qui les relient dans G) est coloriable avec le nombre minimum de couleurs W(H). Ils sont connexes si on peut toujours passer d'un sommet à n'importe quel autre en suivant une (ou plusieurs) arête(s). En 1960, Claude Berge énonça les deux conjectures suivantes : 1. Un graphe est parfait si, et seulement si, son complémentaire (graphe ayant les mêmes sommets et toutes les arêtes complémentaires) l'est. 2. Un graphe est parfait si, et seulement si, il ne contient ni cycle impair, ni complément de cycle impair, sur au moins 5 sommets (un tel graphe est maintenant appelé un graphe de Berge).

La première conjecture (dite « faible ») fut démontrée en 1972 par le Hongrois László Lovász, tandis que la seconde (dite « forte ») le fut en mai 2002 par Maria Chudnovsky, Neil Robertson, Paul Seymour et Robin Thomas après avoir suscité de nombreux travaux.

Une idée fructueuse fut l'étude des graphes minimaux imparfaits (graphes non parfaits pour lesquels il suffit d'enlever un sommet quelconque pour qu'ils le deviennent). De ce point de vue, un outil intéressant est dû à Vašek Chvátal : un graphe minimal imparfait ne contient pas d'étoile déconnectante (i.e. d'ensemble de sommets dont l'un est adjacent à tous les autres et dont la suppression induit un graphe non connexe). L'étude des propriétés des ensembles déconnectants conduit à la fois à des propriétés générales concernant la structure des minimaux imparfaits et la perfection de sous-classes des graphes de Berge [comme les bipartis complets dont l'ensemble des sommets est partitionné en V₁, V₂ tels que deux sommets de V₁ (resp. V₂) ne sont pas reliés mais que tout sommet de V₁ est relié à tous les sommets de V₂]. Ces deux approches complémentaires furent une constante dans les travaux visant à prouver la conjecture forte de Berge ; c'est d'ailleurs en prouvant une propriété structurelle des graphes de Berge que la conjecture forte fut démontrée et devint ainsi un théorème. Une autre technique importante dans cette démonstration consiste à décomposer les graphes en espérant simplifier le problème. Par exemple, un 2-joint est une partition des sommets d'un graphe en deux ensembles V₁ et V₂ d'au moins trois sommets tels qu'il existe des sous-ensembles disjoints A₁, B₁ de V₁ et A₂, B₂ de V₂ tels que tous les sommets de A₁ soient adjacents à tous les sommets de A₂ (idem pour B₁, B₂) et qu'il n'y ait pas d'autre arête reliant V₁ et V₂. On peut alors[...]