Classes héréditaires de graphes – HEREDIA

Les propriétés héréditaires des graphes fournissent un cadre général pour étudier les graphes. Plusieurs théorèmes généraux importants ont été obtenus, et cette approche est un élégant moyen d'unifier diverses notions et techniques de preuve. De plus, les classes héréditaires de graphes jouent un rôle central en théorie des graphes. Outre leur pertinence théorique, elles sont particulièrement intéressantes d'un point de vue algorithmique. Un des problèmes centraux de l'optimisation, la recherche opérationnelle, l'informatique et plus généralement de toute science s'intéressant à l'efficacité est la création d'algorithmes combinatoires efficaces. Les applications touchent des domaines variés, tels que le transport, les télécommunications, la biologie moléculaire et l'ingénierie industrielle. Néanmoins, la plupart des problèmes d'optimisation de graphes étudiés dans ces contextes se révèlent être NP-complets pour des graphes arbitraires. Cela signifie qu'il est hautement improbable que ces problèmes puissent être résolus efficacement (c'est-à-dire en temps polynomial) par un ordinateur. Mais il est possible qu'un tel problème, une fois restreint aux graphes issus des situations réelles étudiées, puisse être résolu en temps polynomial. Une façon appropriée de définir formellement de tels graphes est d'interdire (dans un sens précis) diverses sortes de sous-structures, et ainsi de travailler dans le cadre plus restreint des classes héréditaires. Non-seulement cette approche possède un intérêt pratique, mais elle a aussi engendré d'importants et profonds développements théoriques.

Les classes héréditaires définies par l'interdiction de sous-graphes induits ont donné lieu à de nombreux travaux et la preuve récente du Théorème des Graphes Parfaits, par Chudnovsky, Robertson, Seymour et Thomas, a revigoré l'intérêt pour les classes héréditaires. L'obtention de ce théorème remarquable a nécessité des analyses en profondeur de plusieurs classes héréditaires. Des caractérisations ont été obtenues, et les techniques utilisées ont conduit à des résultats indépendants, comme la caractérisation des graphes sans griffe et des graphes quasi-lignes par Churdnovsky et Seymour. Ces caractérisations ont déjà servi à obtenir d'autres résultats, par exemple pour des problèmes combinatoires sur (des généralisations) des graphes quasi-lignes. D'autres conséquences des méthodes développées par Chudnosvky et al. dans les dix dernières années sont attendues. Il semble particulièrement opportun de consacrer un maximum d'efforts à comprendre et assimiler les techniques introduites, afin de les appliquer à d'autres problèmes et de les développer dans diverses directions.

Les classes de graphes définies par l'exclusion de mineurs sont également de toute première importance. La théorie générale a été principalement développée au cours des trente dernières années. Robertson et Seymour ont publié une série de plus de vingt papiers, créant ainsi un champ complet de recherche et prouvant des résultats profonds. Leurs travaux ont eu des répercussions dans des domaines variés, tels que l'algorithmique, la logique et la complexité. Nous souhaitons travailler dans le contexte plus vaste des graphes d'expansion bornée. Les classes de graphes d'expansion bornée généralisent et unifient dans un large cadre de travail les classes à mineurs exclus, les classes topologiques, les classes de graphes de degré borné, les classes de graphes de nombre de croisements linéaires et certaines graphes aléatoires, par exemple. La notion d'expansion bornée, et une notion encore plus générale appelée "graphes nulle-part denses", correspond de façon profonde à l'idée intuitive de graphe "épars". Ces notions ont été introduites par Nesetril et Ossona de Mendez en 2008. Le cadre de travail ainsi fourni est très prometteur, et devrait permettre une meilleur compréhension de certains phénomènes et paramètres combinatoires dans les classes de graphes restreintes.