Search

Cette thèse réunit en trois articles mon intérêt éclectique pour la théorie des graphes. Le premier problème étudié est la conjecture de Erdos-Faber-Lovász: La réunion de k graphes complets distincts, ayant chacun k sommets, qui ont deux-à-deux au plus un sommet en commun peut être proprement coloriée en k couleurs. Cette conjecture se caractérise par le peu de résultats publiés. Nous prouvons qu’une nouvelle classe de graphes, construite de manière inductive, satisfait la conjecture. Le résultat consistera à présenter une classe qui ne présente pas les limitations courantes d’uniformité ou de régularité. Le deuxième problème considère une conjecture concernant la couverture des arêtes d’un graphe: Si G est un graphe simple avec alpha(G) = 2, alors le nombre minimum de cliques nécessaires pour couvrir l’ensemble des arêtes de G (noté ecc(G)) est au plus n, le nombre de sommets de G. La meilleure borne connue satisfaite par ecc(G) pour tous les graphes avec nombre d’indépendance de deux est le minimum de n + delta(G) et 2n − omega(racine (n log n)), où delta(G) est le plus petit nombre de voisins d’un sommet de G. Notre objectif a été d’obtenir la borne ecc(G), This thesis represents in three articles my eclectic interest for graph theory. The first problem is the conjecture of Erdos-Faber-Lovász: If k complete graphs, each having k vertices, have the property that every pair of distinct complete graphs have at most one vertex in common, then the vertices of the resulting graph can be properly coloured by using k colours. This conjecture is notable in that only a handful of classes of EFL graphs are proved to satisfy the conjecture. We prove that the Erdos-Faber-Lovász Conjecture holds for a new class of graphs, and we do so by an inductive argument. Furthermore, graphs in this class have no restrictions on the number of complete graphs to which a vertex belongs or on the number of vertices of a certain type that a complete graph must contain. The second problem addresses a conjecture concerning the covering of the edges of a graph: The minimal number of cliques necessary to cover all the edges of a simple graph G is denoted by ecc(G). If alpha(G) = 2, then ecc(G)