Structure of graphs : minors and induced trees

Structure de graphes, mineurs et arbres induits Cette thèse traite des questions structurelles de la théorie des graphes qui découlent de motivations algorithmiques.En effet, les problèmes de graphes NP-complets sont typiquement plus faciles dès lors qu'on restreint la classe de graphes.Sur les arbres, qui sont des graphes connexes sans cycles, la programmation dynamique donne souvent un algorithme linéaire. Tous les graphes ne sont pas des arbres, mais il est possible de quantifier à quel point un graphe est plus complexe qu'un arbre.Un outil standard pour cela est la largeur arborescente, qui est profondément liée à la théorie des mineurs, comme nous allons voir dans le premier chapitre. Une autre stratégie consiste à obtenir une structure arborescente en supprimant le moins de sommets possible, comme nous le verrons dans le deuxième chapitre.Le premier chapitre porte sur l'idée de graphes universels pour la relation de mineur.Un graphe est mineur-universel pour une famille de graphes s'il contient comme mineur chaque graphe de la famille. Un résultat célèbre de Robertson, Seymour et Thomas en 1994 montre que la grille 2n times 2n est mineur-universelle pour la famille des graphes planaires à n sommets. Une façon d'affiner ce résultat est de trouver des sous-classes de graphes planaires à n sommets qui admettent une grille mineure-universelle plus petite. On dit que qu'un graphe planaire G admet un dessin sur une grille s'il existe un plongement de G sur une grille, tel que les sommets de G sont des sommets de la grille, et ses arêtes sont des suites de segments dont les jonctions sont placées sur des sommets des la grille. La taille d'un tel dessin est le nombre de sommets de la grille. L'idée est d'établir une relation entre la taille d'un dessin sur une grille d'un graphe H, et la taille de la plus petite grille qui admet H comme mineur.Plutôt que d'affiner le résultat, un autre direction consiste à le généraliser à une classe plus grande.On s'intéresse ici aux graphes de genre borné, le genre d'un graphe étant un paramètre entier qui généralise la notion de planarité.Plus précisément, nous montrons qu'il existe un graphe de genre g mineur-universel pour les graphes à n sommets de genre g, et dont la taille est polynomiale en n et g. Le deuxième chapitre se concentre sur la recherche d'une grande forêt (union de plusieurs arbres) induite dans un graphe. Un cas intéressant est celui où la forêt en question un unique chemin. En 2017, Esperet, Lemoine et Maffray ont conjecturé que tout graphe k-dégénéré avec un chemin à n sommets admet un chemin induit à log n ^{Omega_k(1)} sommets. Nous prouvons que c'est le cas pour plusieurs classes de graphes dégénérés, y compris la classe des graphes excluant un graphe comme mineur topologique. Dans le cas d'une forêt, le théorème d'ErdH{o}s-P'osa stipule que si un graphe n'a pas k cycles disjoints, alors il admet un ensemble de O(klog k) sommets dont l'élimination produit une forêt, appelé textit{feedback vertex set}. Nous obtenons une propriété similaire pour les graphes sans sous-graphe K_{t,t} et sans k cycles indépendants (disjoints et sans arête entre eux). La contrepartie de cette généralisation est un textit{feedback vertex set} dont la taille est logarithmique en la taille du graphe, et cette borne peut être atteinte.