Les travaux classiques de Burlet, Uhry et Burlet, Fonlupt sur les opérations de composition des graphes et leurs algorithmes de reconnaissance sont présents dans presque tous les livres du domaine. Le discours de V. Chvátal au soixante quinzième anniversaire (1992) de William Tutte (un des grands mathématiciens du XXe siècle) était aussi basé sur ces résultats. L'opération de composition du polyèdre des stables [6] est une continuation récente de ces résultats. Notre équipe (certaines remarques de [26] et un résultat non-publié de Burlet et Sebö) continue cette recherche avec des conséquences sur les graphes t-parfaits et parfaits.
Ces études sur les graphes parfaits sont à la jonction de la théorie des graphes et de l'optimisation combinatoire ; elles utilisent les techniques de ces deux domaines. La conjecture des graphes parfaits, posée en 1960, est un des problèmes les plus étudiés ces trente dernières années et, bien que non résolue, la motivation qu'elle représente s'est révélée fructueuse. Parallèlement, il s'agit d'une classe de graphes très importante du point de vue algorithmique : on peut y résoudre de nombreux problèmes d'optimisation combinatoire ; c'est aussi une classe assez générale du point de vue des applications pratiques (" line-graphs ", graphes d'intervalle, graphes de comparabilité, etc.).
Nos résultats établissent des liens entre l'algèbre linéaire et la coloration des graphes, en exploitant la structure polyédrale des graphes parfaits. Certains ont des conséquences algorithmiques [6, 12, 17, 18] (voir un autre aspect de deux de ces articles dans 3.2).
Récemment, dus aux travaux de Boros et Gurvich, Aharoni et Holzman, Alon et Tarsi, (nos visiteurs ou nos hôtes), de nouveaux outils de colorations de graphes se développent. Par notre travail de " referee " et suite aux visites de ces chercheurs, nous nous trouvons engagés dans ces recherches. Cécile Dumas, étudiante au sein de notre équipe, travaille sur ce sujet.