Structures of graph classes and of their excluded minors

Structures des classes de graphes et de leurs mineurs exclus Une classe de graphes est dite close par mineur si elle est close par suppressions d'arêtes, suppressions de sommets, et contractions d'arêtes. Les classes de graphes closes par mineur jouent un rôle central en théorie des graphes grâce à leurs propriétés structurelles et algorithmiques. Dans cette thèse, nous démontrons plusieurs correspondances entre la structure d'une classe de graphes close par mineur et celle de ses mineurs exclus, c'est-à-dire des graphes minimaux parmi ceux qui ne sont pas membres de cette classe. Dans une première partie, nous démontrons une propriété structurelle pour les classes de graphes excluant une grille de hauteur fixée en tant que mineur. Pour ce faire, nous introduisons une nouvelle famille de paramètres de graphes qui généralise la profondeur arborescente et la largeur arborescente. En conséquence, nous obtenons une généralisation du Théorème de la Grille Mineure de Robertson et Seymour. Dans une seconde partie, nous montrons, à travers plusieurs applications, comment utiliser une notion de mineurs enracinés pour résoudre des problèmes sur les mineurs de graphes. La première de ces applications est une preuve simple pour les caractérisations des classes de graphes closes par mineurs ayant une profondeur arborescente en couche ou une largeur linéaire en couche bornée. Une deuxième application consiste en des théorèmes de Structure Produit dans des classes closes par mineurs. Enfin, nous déterminons, à un facteur linéaire près, les nombres chromatiques centrés ainsi que les nombres colorant faibles de toute classe de graphes close par mineur donnée. Dans le cas où cette classe exclut un graphe planaire, nos bornes sont optimales à un facteur constant près.