Chi-boundedness, Geometric Graph Theory, and Burling Graphs

Chi-boundedness, théorie géométrique des graphes, et graphes de Burling Cette thèse porte principalement sur la théorie de la chi-boundedness et la théorie géométrique des graphes. En particulier, nous nous intéressons à un sujet à l'intersection de ces deux théories : les graphes de Burling, une classe de graphes sans triangle avec un nombre chromatique arbitrairement grand, définie par Burling en 1965. Elle a fait depuis son introduction l'objet de nombreux travaux de recherche.Dans cette thèse, nous donnons plusieurs caractérisations équivalentes des graphes de Burling : une définiion combinatoire (les graphes dérivés), une définition axiomatique (les graphes de Burling abstraits), ainsi que quelques définitions géométriques.Nous étudions ensuite la structure de cette classe de graphes à l'aide de la définition des graphes dérivés, ce qui nous permet en particulier d'obtenir un théorème de décomposition.Enfin, nous présentons quelques applications de nos résultats à la théorie de la chi-boundedness. Nous réfutons une conjecture de Scott et Seymour, répondons à une question de Trotignon et fournissons également de nouveaux graphes qui ne sont pas faiblement envahissants, en particulier, les graphes complets à au moins 5 sommets ainsi que certains graphes séries-parallèles.