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 :
L'objectif ici est de donner une introduction aux graphes parfaits.

Quelques références (pas exhaustif).



Retour à la page des sujets.