Le jeu de policiers-voleur sur différentes classes de graphes

Abstract

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.