Résumé :
Un graphe est dit parfait si pour tout sous-graphe induit, le nombre
chromatique est égal à la taille de la plus grande clique. Claude
Berge a formulé en 1960 une conjecture de caractérisation des graphes
parfait par sous-graphes induits interdits. Cette conjecture (dite
conjecture forte des graphes parfaits) a fait l'objet de nombreux
travaux avant d'être démontrée par Chudnovsky, Robertson, Seymour et
Thomas en 2002. Malgré cette percée, de nombreuses questions ouvertes
demeurent, la plus importante étant peut-être celle de l'existence
d'un algorithme efficace de coloration des graphes parfait.
En fait, Grotschel, Lovasz et Schrijver (1984) ont montré que
l'algorithme de l'ellipsoïde permet de colorier les graphes parfaits
en temps polynomial, mais cet algorithme est lent en pratique. Il
n'existe pas à ce jour d'algorithme purement combinatoire. Nous
présenterons des techniques d'optimisation pour les graphes parfaits
qui fonctionnent pour certaines sous-classes : contraction de paires
de sommets bien choisies (les "paires d'amis", even pairs en
anglais), et éliminations successives de sommets.
Nous présenterons des résultats originaux obtenus en collaboration
avec Benjamin Lévêque, Frédéric Maffray, Bruce Reed et Kristina
Vuskovic.