Calcul d'invariants dans les graphes parfaits

Abstract

Nous avons vu que la classe des graphes parfaits était une classe de graphes importantes, en particulier parce qu'elle contient de nombreuses autre classes usuelles, dont les graphes d'intervalles, les graphes de comparabilité ou les graphes triangulés. On peut penser que la preuve des deux conjectures posées par Berge au début des années 1960 clôt la discussion au sujet des graphes parfaits, car cette classe est désormais trés bien connue. P. Seymour mentionne dans un premier axe de recherche, qui consisterait à améliorer la preuve du théorème fort des graphes parfaits. Un autre axe, qui semble a priori plus intéressant, serait d'obtenir un algorithme de construction explicite des graphes de Berge. Dans le même axe, on sait qu'il existe un algorithme de coloriage polynômial, à base de polyèdres et de programmation linéaire : mais existe-t-il un algorithme combinatoire, plus proche de la structure des graphes parfaits