Thèse Benjamin LEVEQUE

Coloration de graphes :
Structures et algorithmes

De nombreux problèmes appliqués peuvent être modélisés par le problème de la coloration des sommets d'un graphe, qui est NP-complet en général mais polynomial sur la classe des graphes parfaits introduite par Berge. L'algorithme de coloration des graphes parfaits, de Grötschel, Lovasz et Schrijver, n'est pas réellement efficace d'un point de vue pratique et il est toujours intéressant de trouver un algorithme ``purement'' combinatoire permettant de colorier les graphes parfaits en temps polynomial. Dans cette thèse, nous donnons plusieurs algorithmes simples et rapides permettant de colorier des sous-classes de graphes parfaits. Ces algorithmes utilisent en particulier la notion de contraction de paire d'amis, introduite par Fonlupt et Uhry, à propos de laquelle plusieurs conjectures sont encore ouvertes. Nous utilisons aussi des algorithmes de parcours comme LexBFS, de Rose, Tarjan et Lueker, pour prouver des résultats structuraux sur les graphes considérés.