Notre équipe est reconnue depuis de nombreuses années dans le domaine de la théorie des graphes. C'est un domaine d'expertise que nous souhaitons continuer de développer. Plus précisément, nous nous intéressons à la coloration des graphes et des hypergraphes. Colorier les sommets d'un graphe consiste à leur affecter des couleurs de sorte qu'il n'y ait pas deux sommets de même couleur reliés par une arête. De plus, on désire généralement utiliser le moins de couleurs possible. 
De nombreux problèmes de Recherche Opérationnelle, et leurs applications aux systèmes de production, s'expriment par la recherche d'une coloration optimale des sommets d'un graphe. Le problème de coloration est en général difficile (NP-complet), mais il est intéressant de trouver des classes de graphes pour lesquelles on peut le résoudre en temps polynomial. Les graphes « parfaits » ont cette propriété, mais le seul algorithme de coloration connu n'est pas utilisable en pratique, et la recherche d'un algorithme efficace reste un défi pour les années à venir. La détermination de sous-classes de graphes parfaits est l'occasion d'étudier des propriétés particulières (le plus souvent algorithmiques).
De nombreux problèmes de Recherche Opérationnelle, et leurs applications aux systèmes de production, s'expriment par la recherche d'une coloration optimale des sommets d'un graphe. Le problème de coloration est en général difficile (NP-complet), mais il est intéressant de trouver des classes de graphes pour lesquelles on peut le résoudre en temps polynomial. Les graphes « parfaits » ont cette propriété, mais le seul algorithme de coloration connu n'est pas utilisable en pratique, et la recherche d'un algorithme efficace reste un défi pour les années à venir. La détermination de sous-classes de graphes parfaits est l'occasion d'étudier des propriétés particulières (le plus souvent algorithmiques).
Nous nous intéressons également à des problèmes de couplages parfaits dans les graphes : il s'agit d'une partition des sommets en paires de voisins. L'existence d'un couplage parfait dans certains graphes précis (notamment dans les graphes bipartis) est liée à de nombreux problèmes pratiques de Recherche Opérationnelle. Nous nous intéressons également au nombre de couplages parfaits (quand on sait garantir l'existence d'au moins un couplage parfait) : le calcul approché de ce nombre a des applications en physique statistique et en chimie moléculaire.