Dans cette thèse nous étudions trois jeux à objectif compétitif sur les graphes. Les jeux à objectif compétitif proposent une approche dynamique des problèmes d'optimisation discrètes. L'idée générale consiste à associer à un problème d'optimisation (coloration, domination, etc.) un jeu combinatoire partisan de la façon suivante. Deux joueurs construisent tour à tour la structure reliée au problème d'optimisation. L'un d'eux cherche à ce que cette structure soit le plus optimale possible, tandis que l'autre essaye de l'en empêcher. Sous l'hypothèse que les deux joueurs jouent optimalement, la taille de la structure obtenue définit un invariant ludique.Nous commençons par étudier une variante 1-impropre du jeu de coloration, qui est le premier et le plus étudié des jeux à objectif compétitif. Dans ce jeu, les joueurs colorient les sommets d'un graphe de sorte que deux sommets adjacents ne partagent jamais la même couleur. Dans la version 1-impropre, un sommet peut avoir au plus un voisin ayant la même couleur que lui. Nous considérons ensuite le jeu de domination, dans lequel les deux joueurs doivent construire un ensemble dominant, c'est-à-dire un ensemble de sommets du graphe tel que tout autre sommet est adjacent à l'un des membres de cet ensemble. Finalement, nous définissons un nouveau jeu à objectif compétitif, relié au problème de coloration distinguante. Dans ce jeu, il s'agit de construire une coloration qui n'est invariante par aucun des automorphismes du graphe. Nous soulevons plusieurs interrogations stimulantes concernant ce nouveau jeu, notamment sur la caractérisation des graphes ayant un invariant ludique infini, par l'existence d'automorphismes d'ordre deux. / In this thesis, we study three competitive optimization graph games. These games allow a dynamic approach to discrete optimization problems, which is an advantageous alternative way to consider these questions. The global idea consists in defining a combinatorial partisan game, associated to the original optimization problem, like coloring, domination, etc. Two players alternatively build the structure related to the optimization problem. One of them tries to obtain a structure as optimal as possible, whereas his opponent wants to prevent him from doing it. Under the hypothesis that both players play optimally, the size of the obtained structure defines a game invariant of the graph.We start by studying a 1-improper variation of the coloring game, which is the first and the most studied competitive optimization graph game. In this game, the players colors the vertices of a graph, such that two adjacent vertices do not share the same color. In the 1-improper version, we allow a vertex to have at most one neighbor with the same color as it. Then, we study the domination game, in which the players have to build a domination set, that is a sub-set of vertices such that any other vertex is adjacent to one of the vertex in this set. Finally, we define a new game, related to the distinguishing coloring problem. This game is about building a vertex-coloring which is preserved by none of the graph automorphisms. We raise some challenging open questions about this new game, especially concerning the characterization of graphs with infinite game invariant, by the existence of order two automorphisms.

Le Théorème des Quatre Couleurs, conjecturé en 1852 et prouvé en 1976, est à l'origine de l'étude des partitions des sommets de graphes peu denses. Il affirme que toute carte plane peut être coloriée avec au plus quatre couleurs différentes, de telle manière que deux régions qui partagent une frontière aient des couleurs différentes. Énoncé en terme de théorie des graphes, cela veut dire que tout graphe planaire, c'est à dire tout graphe qui peut être représenté dans le plan sans que deux arêtes ne se croisent, peut voir son ensemble de sommets partitionné en quatre ensembles tels que chacun de ces ensembles ne contient pas les deux extrémités d'une même arête. Une telle partition est appelée une coloration propre en quatre couleurs. Dans cette thèse, on s'intéresse à l'étude de la structure des graphes peu denses, selon différentes notions de densité. D'une part, on étudie les graphes planaires sans petits cycles, et d'autre part les graphes dont tous les sous-graphes ont un degré moyen peu élevé. Pour ces classes de graphes, on recherche tout d'abord le plus petit nombre de sommets à retirer pour obtenir une forêt, c'est à dire un graphe sans cycles. Cela peut être vu comme une partition des sommets du graphe en un ensemble induisant une forêt et un ensemble de sommets contenant au plus une fraction donnée des sommets du graphe. La motivation première de cette étude est une conjecture d'Albertson et Berman (1976) comme quoi tout graphe planaire admettrait une telle partition où la forêt contient au moins la moitié des sommets du graphe. Dans un second temps, on s'intéresse aux partitions des sommets de ces graphes en deux ensembles, tels que les sous-graphes induits par ces deux ensembles ont des propriétés particulières. Par exemple, ces sous-graphes peuvent être des graphes sans arêtes, des forêts, des graphes de degré borné, ou des graphes dont les composantes connexes ont un nombre borné de sommets. Ces partitions des sommets sont des extensions de la notion de coloration propre de graphe.On montre, pour différentes classes de graphes peu denses, que tous les graphes de ces classes admettent de telles partitions. On s'intéresse également aux aspect algorithmiques de la construction de telles partitions. / The study of vertex partitions of planar graphs was initiated by the Four Colour Theorem, which was conjectured in 1852, and proven in 1976. According to that theorem, one can colour the regions of any planar map by using only four colours, in such a way that any two regions sharing a border have distinct colours. In terms of graph theory, it can be reformulated this way: the vertex set of every planar graph, i.e. every graph that can be represented in the plane such that edges do not cross, can be partitioned into four sets such that no edge has its two endpoints in the same set. Such a partition is called a proper colouring of the graph.In this thesis, we look into the structure of sparse graphs, according to several notions of sparsity. On the one hand, we consider planar graphs with no small cycles, and on the other hand, we consider the graphs where every subgraph has bounded average degree.For these classes of graphs, we first look for the smallest number of vertices that can be removed such that the remaining graph is a forest, that is a graph with no cycles. That can be seen as a partition of the vertices of the graph into a set inducing a forest and a set with a bounded fraction of the vertices of the graph. The main motivation for this study is a the Albertson and Berman Conjecture (1976), which states that every planar graph admits an induced forest containing at least one half of its vertices.We also look into vertex partition of sparse graphs into two sets both inducing a subgraph with some specific prescribed properties. Exemples of such properties can be that they have no edges, or no cycles, that they have bounded degree, or that they have bounded components. These vertex partitions generalise the notion of proper colouring. We show, for different classes of sparse graphs, that every graph in those classes have some specific vertex partition. We also look into algorithmic aspects of these partitions.

Dans cette thèse, nous étudions divers problèmes dont l'objectif est de gérer la croissance d'internet plus efficacement. En effet celle-ci est très vive : 41% pour le pic en 2012. Afin de répondre aux défis posés par cette évolution aux divers acteurs du réseau, des protocoles de gestion et de communication plus intelligents sont nécessaires. Les protocoles de l'Internet furent conçus comme des protocoles point à point. Or, la part de la diffusion de média dans le trafic est prépondérante et en nette hausse, et des projections indiquent qu'en 2016 80-90% du trafic sera engendré par de la diffusion vidéo. Cette divergence entraîne des inefficacités, car des multiples copies d'un message transitent par un lien. Dans cette thèse, nous étudions comment remediér á cette inefficacité. Nos contributions sont organisées selon les couches et les phases de déploiement du réseau. Nous étudions le placement de caches lors de la conception du réseau. Ensuite, pour la gestion d'un réseau, nous regardons quand placer des appareils en veille, en utilisant un mécanisme de cache et en coopération avec des réseaux de distribution. Puis, au niveau de la couche application, nous étudions un problème de maintenance d'arbres équilibrés pour la diffusion de média. Enfin, nous analysons la probabilité de survie des données dans un système de sauvegarde distribuée. Notre travail se fonde à la fois sur des méthodes théoriques (Chaînes de Markov, Programmation Linéaire), mais aussi sur des outils empiriques tels que la simulation et l'expérimentation.