Abstract FR:

La largeur d'arborescence est une notion intéressante d'un point de vue théorique mais également algorithmique puisque beaucoup de problèmes NP-difficiles deviennent polynomiaux quand on se restreint aux graphes de largeur d'arborescence bornée. Elle est étroitement liée à la notion de q-clique-mineur qui lui est duale et à une propriété des familles de graphes dite propriété d'Erdos-Posa. De plus, le caractère borné de la largeur d'arborescence est lié à l'interdiction de graphes planaires en tant que mineurs. Cette thèse est une étude plus précise de ces notions dans le cas de l'interdiction de trois familles, à savoir les circuits de différents types, les prismes et les petites grilles. Nous en déduisons d'une part des bornes polynomiales pour la largeur d'arborescence de certaines familles de graphes et certaines propriétés d'Erdos-Posa et d'autre part de nouveaux algorithmes polynomiaux