Des multiples facettes des graphes circulants

Abstract

Ce document présente une vue synthétique de mes travaux de recherche menés ces cinq dernières années, au sein du LaBRI. Les activités de recherche d'un enseignant-chercheur ne s'inscrivent pas souvent dans un plan de recherche soigneusement pensé. Elles évoluent en fonction de multiples impondérables, dont notamment les rencontres avec d'autres chercheurs ou encore les opportunités "stratégiques" de financement. De ce fait, il n'est pas toujours facile de dégager un fil conducteur qui permette de regrouper un ensemble des résultats obtenus "au fil de l'eau" sans avoir recours à des raccourcis un peu artificiels. Lorsque je me suis efforcé de dégager un point commun à mes travaux, je me suis aperçu que des objets mathématiques bien particuliers n'étaient jamais trés loin de mes activités : les groupes cycliques finis. En creusant un peu plus cette perception, il m'est apparu que mes travaux accordent une place considérable à des graphes élémentaires associés aux groupes cycliques, dits graphes ou encore webs. Ce document est donc consacré à la mise en valeur des multiples facettes de ces graphes. "Facettes" est ici à double sens, puisqu'une partie conséquente de mes résultats est précisément dédiée à la détermination des facettes de certains polytopes associés aux graphes ! Sur la forme, les preuves ont été omises afin d'alléger le texte, à l'exception de quelques preuves sélectionnées pour leur brièveté et pour la pertinence du résultat qu'elles procurent. Des hyperliens pointent vers la version anglaise des preuves manquantes, telles qu'elles figurent dans le recueil d'articles en annexe. Pour faciliter également la lecture, l'index à la fin de l'ouvrage redonne toutes les principales définitions. Sur le fond, ce document est structuré de la manière suivante. Le premier chapitre est consacré aux principaux résultats connus sur les graphes parfaits. Ceci permet de définir les objets mathématiques utilisés par la suite, et de rappeler l'extraordinaire richesse conceptuelle des graphes parfaits. Dans le second chapitre, nous abordons un raffinement de la coloration usuelles des graphes, appelé "coloration circulaire". Cette coloration est à l'origine d'une généralisation récente des graphes parfaits : les "graphes circulaires-parfaits". Nous étudions la possibilité d'une caractérisation analogue � celles des graphes parfaits, que ce soit par sous-graphes exclus ou bien polyédrale. Dans le troisième chapitre, nous nous intéressons à une généralisation naturelle des webs : "les graphes quasi-adjoints". Il s'agit d'une sous-famille des graphes sans griffe, et à ce titre, l'étude de leur polytope des stables est de première importance. Dans le quatrième chapitre, nous menons des investigations directes sur le polytope des stables des graphes sans griffe. La conclusion est donnée dans le dernier et cinquième chapitre, qui contient également une brève présentation de quelques résultats préliminaires quant au calcul en temps polynomial du nombre circulaire-chromatique des graphes circulaires-parfaits et au calcul du nombre de stabilité des graphes quasi-adjoints. Tout repose sur l'introduction d'un nouveau polytope construit à partir des webs ...