Given a graph G = (V, E), two players, Alice and Bob, alternate their turns to choose uncolored edges to be colored. Whenever an uncolored edge is chosen, it is colored by the least positive integer so that no monochromatic cycle is created. Alice¡¦s goal is to minimize the total number of colors used in the game, while Bob¡¦s goal is to maximize it. The game Grundy arboricity of G is the number of colors used in the game when both players use optimal strategies. This thesis discusses the game Grundy arboricity of graphs. It is proved that if a graph G has arboricity k, then the game Grundy arboricity of G is at most 3k − 1. If a graph G has an acyclic orientation D with maximum out-degree at most k, then the game Grundy arboricity of G is at most 3k − 2.

Nous étudions plusieurs problèmes de coloration dans les graphes, pour certains avec une composante ludique. La coloration à distance 2 d'un graphe est une coloration de ses sommets telle que deux sommets à distance au plus 2 ont des couleurs différentes. Le L(p; q)-étiquetage est une généralisation de ce problème ou les contraintes à distance 1 et 2 sont différentes. Nous donnons des résultats pour ces deux problèmes dans plusieurs classes de graphes peu denses (ayant un faible degré moyen maximum).Le jeu de coloration sur un graphe est un jeu ou deux joueurs, Alice et Bob, colorent tour à tour un des sommets non coloriés d'un graphe, construisant ainsi une coloration propre partielle de plus en plus étendue de ce graphe. Alice tente d'étendre la coloration à l'ensemble du graphe, et Bob tente de l'en empêcher. Nous travaillons sur un invariant de graphe, le degré minmax, dont l'étude permet de déduire des résultats pour le jeu de coloration via l'étude d'un problème structurel, la (1; k)-décomposition d'un graphe, c'est-à-dire la partition de ses arêtes en une forêt et un sous-graphe de degré inférieur ou égal à k.Nous travaillons enfin sur une variante du jeu de coloration nommée jeu de coloration d'incidences, ou Alice et Bob colorient les incidences d'un graphe, pour lequel nous donnons une stratégie efficace pour Alice.Enfin, tout au long de notre mémoire, nous étudions les liens entre la notion de coloration est celle de marquage. Un marquage est un ordre sur les sommets (ou arêtes, ou incidences...) d'un graphe possédant des caractéristiques utiles pour le colorer. Pour nos différents problèmes, nous questionnons l'utilité ou les limites de l'usage de cette notion. / We study several problems of graph coloring, some of them with a game component.A 2-distance coloring of a graph is a vertex coloring where two vertices at distanceat most two have different colors. A L(p; q)-labeling is a generalisation of the distance-2coloring where constraints are different at distance 1 and 2. We give results for thesetwo problems in several classes of sparse graphs (with a low maximal average degree).The coloring game on a graph is a game where two players, Alice and Bob, taketurns coloring an uncolored vertex of the graph, constructing together a proper partialcoloring of the graph extending as time moves on. Alice try to extend the coloringto the whole graph, and Bob try to prevent her to win. We study a graph invariant,the minmax degree, who has consequences on the coloring game through the notion of(1; k)-decomposition of a graph, which is the partition of its edge set into a forest and asubgraph of degree bounded by k.We finally study a variant of the coloring game named incidence coloring game, whereAlice and Bob are coloring the incidences of a graph, and for which we give an efficientstrategy for Alice.Finally, during our thesis, we study the connections between coloring and marking,which is an order on the vertices of a graph (or its edges, or its incidences) havingproperties usefull for its coloring. For our problems, we try to determine the utility andthe limits of a marking-based approach of coloring problems.

J'ai étudié trois problèmes d'optimisation dans les graphes et les jeux combinatoires.Tout d'abord, les codes identifiants dans les graphes où les sommets font faces à des failles: les codes cherchent à repérer les failles pour les réparer. On s'est intéressé aux codes identifiants dans les graphes circulants en utilisant des plongements de ces graphes dans des grilles infinies.Ensuite, j'ai étudié le jeu de marquage de sommets et le jeu de coloration d'arêtes: ici deux joueurs se font face, le premier cherche à construire une coloration correcte (ou un marquage correct) et le deuxième cherche à l'en empêcher. Pour le jeu de marquage on s'est intéressé aux changements de stratégie gagnante lorsqu'on modifie le graphe. Pour le jeu de coloration d'arêtes on a donné une stratégie gagnante pour le premier joueur pourvu que le graphe considéré admette une certaine décomposition sur les arêtes. On améliore notamment des résultats sur les graphes planaires.Enfin j'ai étudié les jeux à tas purement de casse: deux joueurs à tour de rôle prennent un tas et le cassent en un certain nombre de tas non vides. On s'intéresse aux stratégies gagnantes lorsque les joueurs jouent sur un unique tas contenant n jetons. Ces jeux de pure casse semblent, à l'oeil nu, être réguliers. On a montré que c'est effectivement le cas pour certains et on a donné un test qui permet de déterminer la régularité cas par cas. Un seul cas ne semble pas correspondre à cette régularité: son comportement reste un mystère.En conclusion, je me suis intéressé à trois problèmes bilatéraux qui utilisent différentes méthodes et qui remplissent des propos différents dans le domaine de la combinatoire / I studied three optimization problems on graphs and combinatorial games.First, identifying codes were studied : vertices couteract faults. Identifying codes help locate the fault to repare it. We focused on circulant graphs by embedding them on infinite grids.Then, the marking and the coloring games were studied : two player games were one player wants to build something (a proper coloration or a proper marking) and the other wants to prevent the first player from doing so. For the marking game we studied the evolution of the strategy when modifying the graph. For the coloring game we defined a new edge-wise decomposition of graphs and we defined a new strategy on this decomposition that improves known results on planar graphs.In the end, I studied pure breaking games : two players take turns to break a heap of tokens in a given number of non-empty heaps. We focused on winning strategies for the game starting with a unique heap on n tokens. These games seem, on first sight, to be all regular : we showed this is the case for some of them and we gave a test to study one game at a time. Only one of these games does not seem to be regular, its behavior remains a mystery.To sum up, I studied three bilateral problems that use different methods and have different purposes in combinatorics