This thesis discusses graph marking game and graph colouring game. Suppose G=(V, E) is a graph. A marking game on G is played by two players, Alice and Bob, with Alice playing first. At the start of the game all vertices are unmarked. A play by either player consists of marking an unmarked vertex. The game ends when all vertices are marked. For each vertex v of G, write t(v)=j if v is marked at the jth step. Let s(v) denote the number of neighbours u of v for which t(u) < t(v), i.e., u is marked before v. The score of the game is $$s = 1+ max_{v in V} s(v).$$ Alice's goal is to minimize the score, while Bob's goal is to maximize it. The game colouring number colg(G) of G is the least s such that Alice has a strategy that results in a score at most s. Suppose r geq 1, d geq 0 are integers. In an (r, d)-relaxed colouring game of G, two players, Alice and Bob, take turns colouring the vertices of G with colours from a set X of r colours, with Alice having the first move. A colour i is legal for an uncoloured vertex x (at a certain step) if after colouring x with colour i, the subgraph induced by vertices of colour i has maximum degree at most d. Each player can only colour an uncoloured vertex with a legal colour. Alice's goal is to have all the vertices coloured, and Bob's goal is the opposite: to have an uncoloured vertex without legal colour. The d-relaxed game chromatic number of a graph G, denoted by $chi_g^{(d)}(G)$ is the least number r so that when playing the (r, d)-relaxed colouring game on G, Alice has a winning strategy. If d=0, then the parameter is called the game chromatic number of G and is also denoted by $chi_g(G)$. This thesis obtains upper and lower bounds for the game colouring number and relaxed game chromatic number of various classes of graphs. Let colg(PT_k) and colg(P) denote the maximum game colouring number of partial k trees and the maximum game colouring number of planar graphs, respectively. In this thesis, we prove that colg(PT_k) = 3k+2 and colg(P) geq 11. We also prove that the game colouring number colg(G) of a graph is a monotone parameter, i.e., if H is a subgraph of G, then colg(H) leq colg(G). For relaxed game chromatic number of graphs, this thesis proves that if G is an outerplanar graph, then $chi_g^{(d)}(G) leq 7-t$ for $t= 2, 3, 4$, for $d geq t$, and $chi_g^{(d)}(G) leq 2$ for $d geq 6$. In particular, the maximum $4$-relaxed game chromatic number of outerplanar graphs is equal to $3$. If $G$ is a tree then $chi_ g^{(d)}(G) leq 2$ for $d geq 2$.

This thesis discusses the game chromatic number of Halin graphs. We shall prove that with a few exceptions, all Halin graphs have game chromatic number 4.

A graph function $f$ is a mapping which assigns each graph $H$ a positive integer $f(H) leq |V(H)|$ such that $f(H)=f(H')$ if $H$ and $H'$ are isomorphic. Given a graph function $f$ and a graph $G$, an $f$-colouring of $G$ is a mapping $c: V(G) o mathbb{N}$ such that every subgraph $H$ of $G$ receives at least $f(H)$ colours, i.e., $|c(H)| geq f(H)$. The $f$-chromatic number, $chi(f,G)$, is the minimum number of colours used in an $f$-colouring of $G$. The $f$-chromatic number of a graph is a natural generalization of the chromatic number of a graph introduced by Nev{s}etv{r}il and Ossena de Mendez. Intuitively, we would like to colour the vertices of a graph $G$ with minimum number of colours subject to the constraint that the number of colours assigned to certain subgraphs must be large enough. The original chromatic number of a graph and many of its generalizations are of this nature. For example, the chromatic number of a graph is the least number of colours needed to colour the vertices of the graph so that any subgraph isomorphic to $K_2$ receives $2$ colours. Acyclic chromatic number of a graph is the least number of colours needed to colour the vertices of the graph so that any subgraph isomorphic to $K_2$ receives $2$ colours, and each cycle receives at least $3$ colours. This thesis studies the game version of $f$-colouring of graphs. Suppose $G$ is a graph and $X$ is a set of colours. Two players, Alice and Bob, take turns colour the vertices of $G$ with colours from the set $X$. A partial colouring of $G$ is legal (with respect to graph function $f$) if for any subgraph $H$ of $G$, the sum of the number of colours used in $H$ and the number of uncoloured vertices of $H$ is at least $f(H)$. Both Alice and Bob must colour legally (i.e., the partial colouring produced needs to be legal). The game ends if either all the vertices are coloured or there are uncoloured vertices but there is no legal colour for any of the uncoloured vertices. In the former case, Alice wins the game. In the latter case, Bob wins the game. The $f$-game chromatic number of $G$, $chi_g(f, G)$, is the least number of colours that the colour set $X$ needs to contain so that Alice has a winning strategy. Observe that if $|X| = |V(G)|$, then Alice always wins. So the parameter $chi_g(f,G)$ is well-defined. We define the $f$-game chromatic index on a graph $G$, $chi'(f,G)$, to be the $f$-game chromatic number on the line graph of $G$. A natural problem concerning the $f$-game chromatic number of graphs is for which graph functions $f$, the $f$-game chromatic number of $G$ is bounded by a constant for graphs $G$ from some natural classes of graphs. In case the $f$-game chromatic number of a class ${cal K}$ of graphs is bounded by a constant, one would like to find the smallest such constant. This thesis studies the $f$-game chromatic number or index for some special classes of graphs and for some special graph functions $f$. The graph functions $f$ considered are the following graph functions: 1. The $d$-relaxed function, ${ m Rel}_d$, is defined as ${ m Rel}_d(K_{1,d+1})=2$ and ${ m Rel}_d(H)=1$ otherwise. 2. The acyclic function, ${ m Acy}$, is defined as ${ m Acy}(K_2)=2$ and ${ m Acy}(C_n)=3$ for any $n geq 3$ and ${ m Acy}(H)=1$ otherwise. 3. The $i$-path function, ${ m Path}_i$, is defined as ${ m Path}_i(K_2)=2$ and ${ m Path}_i(P_i)=3$ and ${ m Path}_i(H)=1$ otherwise, where $P_i$ is the path on $i$ vertices. The classes of graphs considered in the thesis are outerplanar graphs, forests and the line graphs of $d$-degenerate graphs. In Chapter 2, we discuss the acyclic game chromatic number of outerplanar graphs. It is proved that for any outerplanar graph $G$, $chi_g({ m Acy},G) leq 7$. On the other hand, there is an outerplanar graph $G$ for which $chi_g({ m Acy},G) = 6$. So the best upper bound for $chi_g({ m Acy},G)$ for outerplanar graphs is either $6$ or $7$. Moreover, we show that for any integer $n$, there is a series-parallel graph $G_n$ with $chi_g({ m Acy}, G_n) > n$. In Chapter 3, we discuss the ${ m Path}_i$-game chromatic number for forests. It is proved that if $i geq 8$, then for any forest $F$, $chi_g({ m Path}_i, F) leq 9$. On the other hand, if $i leq 6$, then for any integer $k$, there is a tree $T$ such that $chi_g({ m Path}_i, T) geq k$. Chapter 4 studies the $d$-relaxed game chromatic indexes of $k$-degenerated graphs. It is proved that if $d geq 2k^2 + 5k-1$ and $G$ is $k$-degenerated, then $chi'_{ m g}({ m Rel}_d,G) leq 2k + frac{(Delta(G)+k-1)(k+1)}{d-2k^2-4k+2}$. On the other hand, for any positive integer $ d leq Delta-2$, there is a tree $T$ with maximum degree $Delta$ for which $chi'_g({ m Rel}_d, T) geq frac{2Delta}{d+3}$. Moreover, we show that $chi'_g({ m Rel}_d, G) leq 2$ if $d geq 2k + 2lfloor frac{Delta(G)-k}{2} floor +1$ and $G$ is a $k$-degenerated graph.

This thesis discusses colouring, circular list colouring and adapted game colouring of graphs. For colouring, this thesis obtains a sufficient condition for a planar graph to be 3-colourable. Suppose G is a planar graph. Let H_G be the graph with vertex set V (H_G) = {C : C is a cycle of G with |C| ∈ {4, 6, 7}} and edge set E(H_G) = {CiCj : Ci and Cj have edges in common}. We prove that if any 3-cycles and 5-cycles are not adjacent to i-cycles for 3 ≤ i ≤ 7, and H_G is a forest, then G is 3-colourable. For circular consecutive choosability, this thesis obtains a basic relation among chcc(G), X(G) and Xc(G) for any finite graph G. We show that for any finite graph G, X(G) − 1 ≤ chcc(G) < 2 Xc(G). We also determine the value of chcc(G) for complete graphs, trees, cycles, balanced complete bipartite graphs and some complete multi-partite graphs. Upper and lower bounds for chcc(G) are given for some other classes of graphs. For adapted game chromatic number, this thesis studies the adapted game chromatic number of various classes of graphs. We prove that the maximum adapted game chromatic number of trees is 3; the maximum adapted game chromatic number of outerplanar graphs is 5; the maximum adapted game chromatic number of partial k-trees is between k + 2 and 2k + 1; and the maximum adapted game chromatic number of planar graphs is between 6 and 11. We also give upper bounds for the Cartesian product of special classes of graphs, such as the Cartesian product of partial k-trees and outerplanar graphs, or planar graphs.

La thèse porte sur les deux thèmes des Jeux combinatoires et de la théorie des graphes. Elle est divisée en deux parties.1) Le jeu de Domination et ses variantes: Il s'agit d'un jeu combinatoire qui consiste à marquer les sommets d'un graphe de telle sorte qu'un sommet marqué n'ait aucun voisin marqué. Le joueur marquant le dernier sommet est déclaré gagnant. Le calcul des stratégies gagnantes étant NP-difficile pour un graphe quelconque, nous avons étudié des familles particulières de graphes comme les chemins, les scies ou les chenilles. Pour ces familles on peut savoir en temps polynomial si un graphe est perdant. Nous avons également étudié 28 variantes du jeu de domination, dont les 12 variantes définies par J. Conway sur un jeu combinatoire quelconque. 2) Le nombre chromatique ludique des arbres: Ce paramètre est calculé à partir d'un jeu de coloration où Alice et Bob colorient alternativement et proprement un sommet d'un graphe G avec l'une des k couleurs. L'objectif d'Alice est de colorier complètement le graphe alors que Bob doit l'en empêcher. Nous nous sommes intéressés au jeu avec 3 couleurs sur un arbre T. Nous souhaitons déterminer les arbres ayant un nombre chromatique ludique 3, soit ceux pour lesquels Alice a une stratégie gagnante avec 3 couleurs. Ce problème semblant difficile à résoudre sur les arbres, nous avons résolu des sous-familles: les 1-chenilles puis les chenilles sans trous. / Part 1: Domination Game and its variantsDomination game is a combinatorial game that consists in marking vertices of a graph so that a marked vertex has no marked neighbors. The first player unable to mark a vertex loses the game.Since the computing of winning strategies is an NP-hard problem for any graphs, we examine some specific families of graphs such as complete k-partite graphs, paths or saws. For these families, we establish the set of losing elements. For other families, such as caterpillars, we prove that exists a polynomial algorithm for the computation of outcome and winning strategies. No polynomial algorithm has been found to date for more general families, such as trees.We also study 28 variants of Domination game, including the 12 variants defined by J. Conway for any combinatorial game. Using game functions, we find the set of losing paths for 10 of these 12 variants. We also investigate 16 variants called diameter, for instance when rules require to play on the component that has the largest diameter.Part 2: The game chromatic number of treesThis parameter is computed from a coloring game: Alice and Bob alternatively color the vertices of a graph G, using one of the k colors in the color set. Alice has to achieve the coloring of the entire graph whereas Bob has to prevent this. Faigle and al. proved that the game chromatic number of a tree is at most 4. We undertake characterization of trees with a game chromatic number of 3. Since this problem seems difficult for general trees, we focus on sub-families: 1-caterpillars and caterpillars without holes.For these families we provide the characterization and also compute winning strategies for Alice and Bob. In order to do so, we are led to define a new notion, the bitype, that for a partially-colored graph G associates two letters indicating who has a winning strategy respectively on G and G with an isolated vertex. Bitypes allow us to demonstrate several properties, in particular to compute the game chromatic number of a graph from the bitypes of its connected components.