Coloration de graphes épars

Cette thèse a pour thème la coloration de diverses classes de graphes épars. Shearer montra en 1983 [She83] que le ratio d'indépendance des graphes sans triangle de degré maximal d est au moins (1-o(1))ln d/d, et 13 ans plus tard Johansson [Joh96] démontra que le nombre chromatique de ces graphes est au plus O(d/ln d) quand d tend vers l'infini. Ce dernier résultat fut récemment amélioré par Molloy [Mol19], qui montra que la borne (1+o(1))d/ln d est valide quand d tend vers l'infini.Tandis que le résultat de Molloy s'exprime à l'aide d'un paramètre global, le degré maximal du graphe, nous montrons qu'il est possible de l'étendre à la coloration locale. Il s'agit de la coloration par liste, où la taille de la liste associée à chaque sommet ne dépend que de son degré. Avec une méthode différente se basant sur les propriétés de la distribution hard-core sur les ensembles indépendants d'un graphe, nous obtenons un résultat similaire pour la coloration fractionnaire locale, avec des hypothèses plus faibles. Nous démontrons également un résultat concernant la coloration fractionnaire locale des graphes où chaque sommet est contenu dans un nombre borné de triangles, et une borne principalement optimale sur le taux d'occupation — la taille moyenne des ensembles indépendants — de ces graphes. Nous considérons également les graphes de maille 7, et prouvons des résultats similaires qui améliorent les bornes précédemment connues quand le degré maximal du graphe est au plus 10^7. Finalement, pour les graphes d-réguliers où d vaut 3, 4, ou 5, de maille g variant entre 6 et 12, nous démontrons de nouvelles bornes inférieures sur le ratio d'indépendance.Le Chapitre 2 est dédié à la coloration à distance t d'un graphe, qui généralise la notion de coloration forte des arêtes. Nous cherchons à étendre le théorème de Johansson à la coloration à distance t, par l'exclusion de certains cycles. Le résultat de Johansson s'obtient par exclusion des triangles, ou des cycles de taille k pour n'importe quelle valeur de k. Nous montrons que l'exclusion des cycles de taille 2k, pour n'importe quel k>t, a un effet similaire sur le nombre chromatique à distance t, et sur l'indice chromatique à distance t+1. En outre, quand t est impair, une conclusion similaire peut se faire pour le nombre chromatique à distance t par l'exclusion des cycles de d'une taille impaire fixée valant au moins 3t. Nous étudions l'optimalité de ces résultats à l'aide de constructions de nature combinatoire, algébrique, et probabiliste.Dans le Chapitre 3, nous nous intéressons à la densité bipartie induite des graphes sans triangle, un paramètre relaxant celui de la coloration fractionnaire. Motivés par une conjecture de Esperet, Kang, et Thomassé [EKT19], qui prétend que la densité bipartie induite de graphes sans triangle de degré moyen d est au moins de l'ordre de ln d, nous démontrons cette conjecture quand d est suffisamment grand en termes du nombre de sommets n, à savoir d est au moins de l'ordre de (n ln n)^(1/2). Ce résultat ne pourrait être amélioré que par une valeur de l'ordre de ln n, ce que nous montrons à l'aide d'une construction reposant sur le processus sans triangle. Nos travaux se ramènent à un problème intéressant, celui de déterminer le nombre chromatique fractionnaire maximal d'un graphe épars à n sommets. Nous prouvons des bornes supérieures non triviales pour les graphes sans triangle, et pour les graphes dont chaque sommet appartient à un nombre borné de triangles.Cette thèse est reliée aux nombres de Ramsey. À ce jour, le meilleur encadrement connu sur R(3,t) nous est donné par le résultat de Shearer, et par une analyse récente du processus sans triangle [BoKe13+,FGM13+], ce qui donne(1-o(1)) t²/(4 ln t) < R(3,t) < (1+o(1)) t²/ln t. (1)Beaucoup de nos résultats ne pourraient être améliorés à moins d'améliorer par la même occasion (1), ce qui constituerait une révolution dans la théorie de Ramsey quantitative.