La théorie des graphes est un outil puissant d'investigation des structures combinatoires complexes. Notre recherche porte sur le développement de cette théorie et sur ses applications, notamment dans le domaine des communications dans les réseaux.

En théorie des graphes nous nous intéressons à des problèmes classiques dans leurs développements les plus récents et nous introduisons de nouveaux axes de recherche. Notre expertise en théorie des graphes se situe en particulier dans les problèmes liés à l'hamiltonisme, aux colorations, et au calcul d'invariants. La notion de coloration orientée, par exemple, a été introduite et développée au LaBRI et se trouve actuellement largement étudiée dans la communauté internationale. Notre travail porte aussi sur l'analyse de paramètres de graphes généraux et de graphes plus fortement structurés (planaires, de largeur arborescente bornée, ...), le calcul de tables de routage compactes, d'étiquetage de distance, les algorithmes pour les communications, le codage des graphes, les jeux sur les graphes.