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)

On étudie la conjecture des graphes jumeaux dénombrables, cas spécifique d’une conjecture de Thomassé, qui dit que le nombre de jumeaux d’un graphe dénombrable ( ses sous-graphes propres desquels il est aussi un sous-graphe propre) est soit nul, soit infini. On commence par étudier les graphes auto-abrités, que nous définissons, et en utilisant notre classification de ces graphes nous prouvons la conjecture dans certains cas, en précisant la cardinalité exacte du nombre de jumeaux. Nous donnons également des contre-exemples à l’article de l’arXiv «Self-contained graphs»., We make progress on the Graph Alternative Conjecture, a special case of a conjecture of Thomassé which says that the number of twins of a countable graph (i.e. its proper subgraphs of which that graph is also a proper subgraph) is either null or infinite. We begin by studying self-embedded graphs, which we define, and using our classification of these graphs, we prove the conjecture in some cases while specifying the exact number of twins. We also give counter-examples to a paper on arXiv called "Self-contained graphs".

Ce mémoire étudie le jeu de policiers-voleur et contient trois articles, chacun portant sur une classe de graphes spécifique. Dans le premier chapitre, la notation et les définitions de base de la théorie de graphe qui nous serons utiles sont introduites. Bien que chaque article comporte une introduction citant les concepts et résultats pertinents, le premier chapitre de ce mémoire contient aussi une introduction générale au jeu de policiers-voleur et présente certains des résultats majeurs sur ce jeu. Le deuxième chapitre contient l’article écrit avec Seyyed Aliasghar Hosseini et Peter Bradshaw portant sur le jeu de policiers-voleurs sur les graphes de Cayley abéliens. Nous améliorons la borne supérieure sur le cop number de ces graphes en raffinant les méthodes utilisées précédemment par Hamidoune, Frankl et Bradshaw. Le troisième chapitre présente l’article concernant le cop number des graphes 2K2-libres. Plus précisément, il est prouvé que 2 policiers peuvent toujours capturer le voleur sur ces graphes, prouvant ainsi la conjecture de Sivaraman et Testa. Finalement, le quatrième chapitre est l’article écrit avec Samuel Yvon et porte sur les graphes qui ont cop number 4. Nous montrons que tous ces graphes ont au moins 19 sommets. En d’autres mots, 3 policiers peuvent toujours capturer le voleur sur tout graphe avec au plus 18 sommets, ce qui répond par la négative à une question de Andreae formulée en 1986. Un pan important de la preuve est faite par ordinateur; ce mémoire contient donc une annexe comprenant le code utilisé., This thesis studies the game of cops and robbers and consists of three articles, each considering a specific class of graphs. In the first chapter, notation and basic definitions of graph theory are introduced. Al- though each article has an introduction citing the relevant concepts and results, the first chapter of this thesis also contains a general introduction to the game of cops and robbers and presents some of its major results. The second chapter contains the paper written with Seyyed Aliasghar Hosseini and Peter Bradshaw on the game of cops and robbers on abelian Cayley graphs. We improve the upper bound on the cop number of these graphs by refining the methods used previously by Hamidoune, Frankl and Bradshaw. The third chapter presents the paper concerning the cop number of 2K2-free graphs. More precisely, it is proved that 2 cops can always catch the robber on these graphs, proving a conjecture of Sivaraman and Testa. Finally, the fourth chapter is the paper written with Samuel Yvon which deals with graphs of cop number 4. We show that such graphs have at least 19 vertices. In other words, 3 cops can always catch the robber on any graph with at most 18 vertices, which answers in the negative a question by Andreae from 1986. An important part of the proof is by computer; this thesis thus has an appendix containing the code used., Réalisé avec le support financier du Conseil de recherches en sciences naturelles et en génie du Canada (CRSNG) et du Fonds de Recherche du Québec – Nature et technologies (FRQNT).

Le présent mémoire traite du problème de domination éternelle dans les graphes. Nous considérons trois modèles différents du problème, à savoir le modèle du garde, de l’anglais one-guard moves model, le modèle des gardes, de l’anglais all-guards move model, et le modèle fractionnaire. Dans un premier temps, nous étudions quelques questions fondamentales liées à la relation entre le nombre de stabilité́, le nombre de domination éternelle et la cardinalité́ d’une couverture minimum d’un graphe dans le modèle du garde. Dans un second temps, nous proposons une stratégie qui borne supérieurement par mi/7 + O(m+n) le nombre de domination éternelle de la grille forte Pm ⊠ Pn dans le modèle des gardes. Finalement, nous nous inspirons de quelques résultats de la théorie fractionnaire des graphes pour introduire une analogue fractionnaire du problème., In this thesis, we study the eternal domination problem in graphs. We consider three different models of the problem, namely the one-guard moves model, the all-guards move model and the fractional model. First of all, we study some fundamental questions related to the relation between the independence number, the eternal domination number and the clique cover number of a graph in the one-guard moves model. Second, we propose a strategy which gives an upper bound of mi/7 + O(m+n) on the eternal domination number of the strong grid Pm ⊠ Pn in the all-guards move model. In the end, inspired by the fundamental results in fractional graph theory, we introduce a fractional analogue of the eternal domination problem.