Graphes parfaits.

Pour tout graphe G, on sait que χ(G) ≥ ω(G), où χ(G) est le nombre chromatique et ω(G) le cardinal maximum d'une clique. Les graphes parfaits sont ceux tels que pour tout H sous-graphe de G, on a l'égalité χ(H)=ω(H).

La classe des graphes parfaits est probablement l'une de celle qui a été le plus étudiée, notamment à cuase de ses bonnes propriétés, par le fait qu'elle englobe environ une centaine d'autres classes connues, et par les fameuses conjectures qui lui sont associées :

• La conjecture faible des graphes parfaits (énoncée par Berge en 1960, prouvée par Lovasz en 1972) : si G est parfait, alors son complementaire est aussi parfait.
• La conjecture forte des graphes parfaits (énoncée par Berge en 1960, prouvée par Chudnovsky, Robertson, Seymour et Thomas en 2002) : G est parfait si et seulement si ni lui, ni son complémentaire ne contiennent de trou de longeur impaire (un trou est un cycle sans corde de longueur ≥ 4).
• La reconnaissance en temps polynomial des graphes parfaits (résolu par Chudnovsky, Cornuejols, Liu, Seymour et Vuskovic en 2002).
  

L'objectif ici est de donner une introduction aux graphes parfaits.

• La condition d'hérédité est importante dans la définition des graphes parfaits pour que la classe soit intéressante. A ce propos, quel est le plus petit graphe G qui vérifie χ(G)=ω(G) mais qui n'est pas parfait ?
• Présenter des exemples de classes dont les graphes sont parfaits. Y en a-t-il dans les classes vues en cours ? Avez-vous d'autres exemples ?
  
• Est-ce que vous pouvez prouver que ces exemples vérifient le théorème fort des graphes parfaits ?
  
• Un aspect important des graphes parfaits est qu'il existe un algorithme polynomial de calcul du nombre chromatique. Décrit par Grotschel, Lovasz et Schrijver, il est basé sur de la programmation linéaire et dépasse un peu le cadre de ce cours. Par contre, pour les classes que vous avez présentées, avez-vous des algorithmes polynomiaux de calcul du nombre chromatique ?
• Présenter une preuve du théorème faible des graphes parfaits.
• Présenter d'autres résultats ou classes de graphes parfaits, qui vous plaisent.
  

Quelques références (pas exhaustif).

• Introduction to Graph Theory, livre de D. West, Prentice Hall (2001). La section 8.1 en particulier est consacrée aux graphes parfaits.
  
• Algorithmic graph theory and perfect graphs, livre de M. Golumbic, Academic Press (1980). En plus des résultats généraux sur les graphes parfaits, contient l'étude de plusieurs classes particulières de graphes parfaits.
• How the proof of the strong perfect graph conjecture was found, de P. Seymour dans la Gazette des Mathematiciens (2006). L'histoire de la démonstration du théorème fort des graphes parfaits par P. Seymour.
  

Retour à la page des sujets.