Structures Interdites – Stint

Les sous-graphes induits jouent un rôle central dans la théorie des graphe, tant dans ses aspects structurels qu'algorithmiques. Un graphe H est un sous-graphe induit d'un graphe G si on peut obtenir H à partir de G en enlevant des sommets. Parmi toutes les notions de sous-graphes, celle-ci est la plus forte, et de ce fait être sans-H (c'est-à-dire ne pas contenir H en tant que sous-graphe induit) n'est pas très restrictif. Des notions plus faibles de sous-graphes, comme par exemple la notion de mineur de graphe, est maintenant bien comprise, et la prochaine étape de la théorie des graphes est sans doute la compréhension de l'exclusion de structures induites. La question centrale de notre projet est la suivante :

Etant donné une famille (éventuellement infinie) F de graphes, quelles sont les propriété d'un graphe sans aucun sous-graphe induit membre de F ?

Cette question est la clef de nombreux problèmes, car beaucoup de classes de graphes importante sont définies par sous-graphes induits exclus. Ce domaine est actuellement en croissance rapide, et des techniques et outils se développent aujourd'hui.

Notre premier but est d'établir des bornes sur plusieurs paramètres classiques pour les graphes sans-F, comme par exemple le nombre de clique, le nombre de stabilité et le nombre chromatique. Un second but est de concevoir des algorithmes efficaces pour décider si un graphe est sans-F et de calculer ou d'approximer des paramètres. Nous envisageons aussi d'étudier la contrepartie de toutes ces notions dans le cas orienté.

A cette fin, nous proposons d'utiliser et de développer différentes techniques de preuve, parois récentes, comme la description structurelle des classes de graphes, le lemme de régularité, les limites de graphes, les algèbre de drapeau, la VC-dimension, le déchargement ainsi que les preuves assistées par ordinateur.