Abstract FR:

La classe des graphes que nous allons considerer (c. -a-d. Les graphes parfaits) fut definie au debut des annees 60 par claude berge ; il proposa, a la meme epoque, deux conjectures les concernant. Tandis que l'une fut prouvee en 1971 par lovasz, l'autre, connue sous le nom de conjecture forte des graphes parfaits, reste ouverte depuis pres de 40 ans. L'interet des graphes parfaits est multiple, notamment par la verification de cette belle conjecture, mais aussi, et surtout, parce qu'ils apparaissent naturellement dans de nombreux problemes pratiques. Nous nous interesserons, dans un premier temps, aux graphes minimaux imparfaits (c. -a-d. Aux graphes imparfaits dont tous les sous-graphes propres sont parfaits) qui semblent etre un des moyens les plus interessants pour aborder la conjecture forte de berge, avant de nous consacrer, plus particulierement, a l'etude de la sous-classe des graphes minimaux imparfaits p5-libres. Enfin, nous terminerons cette these par le probleme de la coloration, np-complet en general, mais qui devient polynomial pour les graphes parfaits, comme l'ont montre grotschel, lovasz et schrijver en 1981. A cet effet, nous presenterons differents algorithmes polynomiaux permettant d'obtenir une coloration optimale de certaines des classes de graphes parfaits que nous aurons precedemment etudiees