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.

<p>The densest subgraph problem is an important problem with both theoretical and practical significance. We consider a variant of the problem, the directed densest subgraph problem, under the partially dynamic setting of edge insertions only. We give a algorithm maintaining a (1-ε)-approximate directed densest subgraph in O(log³n/ε⁶) amortized time per edge insertion, based on earlier work by Chekuri and Quanrud. This result partially improves on an earlier result by Sawlani and Wang, which guarantees O(log⁵n/ε⁷) worst case time for edge insertions and deletions.</p>

Given a graph G and an initial colouring of its vertices with two colours, say black and white, an irreversible k-threshold conversion process on G is an iterative process in which a white vertex becomes permanently coloured black at time t if at least k of its neighbours are coloured black at time t-1. A set S of vertices is an irreversible k-threshold conversion set (k-conversion set) of G if the initial colouring in which the vertices of S are black and the others are white results in the whole vertex set becoming black eventually. In the case where G is (k+1)-regular, it can be shown that the k-conversion sets coincide with the so-called feedback vertex sets, or decycling sets. In this dissertation we study the size and structure of minimum k-conversion sets in several classes of graphs. We examine conditions that lead to equality and inequality in existing bounds on the minimum size of a k-conversion set of G, for k- and (k+1)-regular graphs G. Furthermore, we derive new sharp lower bounds on this number for regular graphs of degree ranging from k+1 to 2k-1 and for graphs of maximum degree k+1. We determine exact values of the minimum size of a k-conversion set for certain classes of trees. We show that every (k+1)-regular graph has a minimum k-conversion set that avoids certain structures in its induced subgraph. These results lead to new proofs of several known results on colourings and forest partitions of (k+1)-regular graphs and graphs of maximum degree k+1. / Graduate

Un k-coloriage total d'un graphe G est un coloriage de V(G)cup E(G) utilisant (1,2,…,k) couleurs tel qu'aucune paire d'éléments adjacents ou incidents ne reçoivent la même couleur. Le nombre chromatique total chi''(G) est le plus petit entier k tel que G admette un k-coloriage total. Dans le chapitre 2, nous étudions la coloration totale de graphe planaires et obtenons 3 résultats : (1) Soit G un graphe planaire avec pour degré maximum Deltageq8. Si toutes les paires de 6-cycles cordaux ne sont pas adjacentes dans G, alors chi''(G)=Delta+1. (2) Soit G un graphe planaire avec pour degré maximum Deltageq8. Si tout 7-cycle de G contient au plus deux cordes, alors chi''(G)=Delta+1. (3) Soit G un graphe planaire sans 5-cycles cordaux qui s'intersectent, c'est à dire tel que tout sommet ne soit incident qu'à au plus un seul 5-cycle cordal. Si Deltageq7, alors chi''(G)=Delta+1.Une relation L est appelé assignation pour un graphe G s'il met en relation chaque x à une liste de couleur. S'il est possible de colorier G tel que la couleur de chaque x soit présente dans la liste qu'il lui a été assignée, et qu'aucune paire de sommets adjacents n'aient la même couleur, alors on dit que G est L-coloriable. Un graphe G est k-selectionable si G est L-coloriable pour toute assignation L de G qui satisfait |L(v)geq k| pour tout x. Nous démontrons que si chaque 5-cycle de G n'est pas simultanément adjacent à des 3-cycles et des 4-cycles, alors G est 4-sélectionable. Dans le chapitre 3, nous prouvons que si aucun des 5-cycles de G n'est adjacent à un 4-cycles, alors chi'_l(G)=Delta et chi''_l(G)=Delta+1 si Delta(G)geq8, et chi'_l(G)leqDelta+1 et chi''_l(G)leqDelta+2 si Delta(G)geq6.Dans le chapitre 4, nous allons fournir une définition du coloriage total somme-des-voisins-distinguant, et passer en revue les progrgrave{e}s et conjecture concernant ce type de coloriage. Soit f(v) la somme des couleurs d'un sommet v et des toutes les arrêtes incidentes à v. Un k-coloriage total somme-des-voisins-distinguant de G est un k coloriage total de G tel que pour chaque arrête uvin E(G), f(u)eq f(v). Le plus petit k tel qu'on ai un tel coloriage sur G est appelé le nombre chromatique total somme-des-voisins-distinguant, noté chi''_{sum} (G). Nous avons démontré que si un graphe G avec degré maximum Delta(G) peut être embedded dans une surface Sigma de caractéristique eulérienne chi(Sigma)geq0, alors chi_{sum}^{''}(G)leq max{Delta(G)+2, 16}.Une forêt linéaire est un graphe pour lequel chaque composante connexe est une chemin. L'arboricité linéaire la(G) d'un graphe G tel que définie est le nombre minimum de forêts linéaires dans G, dont l'union est égale à V(G). Dans le chapitre 5, nous prouvons que si G est une graphe planaire tel que tout 7-cycle de G contienne au plus deux cordes, alors G est linéairementleft lceil frac{Delta+1}{2}ightceil-sélectionable si Delta(G)geq6, et G est linéairement left lceil frac{Delta}{2}ightceil-sélectionable si Delta(G)geq 11. / A k-total-coloring of a graph G is a coloring of V(G)cup E(G) using (1,2,…,k) colors such that no two adjacent or incident elements receive the same color．The total chromatic number chi''(G) is the smallest integer k such that G has a k-total-coloring. In chapter 2, we study total coloring of planar graphs and obtain three results: (1) Let G be a planar graph with maximum degree Deltageq8. If every two chordal 6-cycles are not adjacent in G, then chi''(G)=Delta+1. (2) Let G be a planar graph G with maximum degree Deltageq8. If any 7-cycle of G contains at most two chords, then chi''(G)=Delta+1. (3) Let G be a planar graph without intersecting chordal 5-cycles, that is, every vertex is incident with at most one chordal 5-cycle. If Deltageq7, then chi''(G)=Delta+1.A mapping L is said to be an assignment for a graph G if it assigns a list L(x) of colors to each xin V(G)cup E(G). If it is possible to color G so that every vertex gets a color from its list and no two adjacent vertices receive the same color, then we say that G is L-colorable. A graph G is k-choosable if G is an L-colorable for any assignment L for G satisfying |L(x)|geq k for every vertex xin V(G)cup E(G). We prove that if every 5-cycle of G is not simultaneously adjacent to 3-cycles and 4-cycles, then G is 4-choosable. In chapter 3, if every 5-cycles of G is not adjacent to 4-cycles, we prove that chi'_l(G)=Delta, chi''_l(G)=Delta+1 if Delta(G)geq8, and chi'_l(G)leqDelta+1, chi''_l(G)leqDelta+2 if Delta(G)geq6.In chapter 4, we will give the definition of neighbor sum distinguishing total coloring. Let f(v) denote the sum of the colors of a vertex v and the colors of all incident edges of v. A total k-neighbor sum distinguishing-coloring of G is a total k-coloring of G such that for each edge uvin E(G), f(u)eq f(v). The smallestnumber k is called the neighbor sum distinguishing total chromatic number, denoted by chi''_{sum} (G). Pilsniak and Wozniak conjectured that for any graph G with maximum degree Delta(G) holds that chi''_{sum} (G)leqDelta(G)+3. We prove for a graph G with maximum degree Delta(G) which can be embedded in a surface Sigma of Euler characteristic chi(Sigma)geq0, then chi_{sum}^{''}(G)leq max{Delta(G)+2, 16}.Lastly, we study the linear L-choosable arboricity of graph. A linear forest is a graph in which each component is a path. The linear arboricity la(G) of a graph G is the minimum number of linear forests in G, whose union is the set of all edges of G. A list assignment L to the edges of G is the assignment of a set L(e)subseteq N of colors to every edge e of G, where N is the set of positive integers. If G has a coloring varphi (e) such that varphi (e)in L(e) for every edge e and (V(G),varphi^{-1}(i)) is a linear forest for any iin C_{varphi}, where C_{varphi }=left { varphi (e)|ein E(G)ight }, then we say that G is linear L-colorable and varphi is a linear L-coloring of G. We say that G is linear k-choosable if it is linear L-colorable for every list assignment L satisfying |L(e)| geq k for all edges e. The list linear arboricity la_{list}(G) of a graph G is the minimum number k for which G is linear k-list colorable. It is obvious that la(G)leq la_{list}(G). In chapter 5, we prove that if G is a planar graph such that every 7-cycle of G contains at most two chords, then G is linear left lceil frac{Delta+1}{2}ightceil-choosable if Delta(G)geq6, and G is linear left lceil frac{Delta}{2}ightceil-choosable if Delta(G)geq 11.

Dans cette thèse, nous nous intéressons à differentes colorations des sommets d’un graphe et aux homomorphismes de graphes. Nous nous intéressons plus spécialement aux graphes planaires et aux graphes peu denses. Nous considérons la coloration propre des sommets, la coloration acyclique, la coloration étoilée, lak-forêt-coloration, la coloration fractionnaire et la version par liste de la plupart de ces concepts.Dans le Chapitre 2, nous cherchons des conditions suffisantes de 3-liste colorabilité des graphes planaires. Ces conditions sont exprimées en termes de sous-graphes interdits et nos résultats impliquent plusieurs résultats connus.La notion de la coloration acyclique par liste des graphes planaires a été introduite par Borodin, Fon-Der Flaass, Kostochka, Raspaud, et Sopena. Ils ont conjecturé que tout graphe planaire est acycliquement 5-liste coloriable. Dans le Chapitre 3, on obtient des conditions suffisantes pour qu’un graphe planaire admette une k-coloration acyclique par liste avec k 2 f3; 4; 5g.Dans le Chapitre 4, nous montrons que tout graphe subcubique est 6-étoilé coloriable.D’autre part, Fertin, Raspaud et Reed ont montré que le graphe de Wagner ne peut pas être 5-étoilé-coloriable. Ce fait implique que notre résultat est optimal. De plus, nous obtenons des nouvelles bornes supérieures sur la choisissabilité étoilé d’un graphe planaire subcubique de maille donnée.Une k-forêt-coloration d’un graphe G est une application ¼ de l’ensemble des sommets V (G) de G dans l’ensemble de couleurs 1; 2; ¢ ¢ ¢ ; k telle que chaque classede couleur induit une forêt. Le sommet-arboricité de G est le plus petit entier ktel que G a k-forêt-coloration. Dans le Chapitre 5, nous prouvons une conjecture de Raspaud et Wang affirmant que tout graphe planaire sans triangles intersectants admet une sommet-arboricité au plus 2.Enfin, au Chapitre 6, nous nous concentrons sur le problème d’homomorphisme des graphes peu denses dans le graphe de Petersen. Plus précisément, nous prouvons que tout graphe sans triangles ayant un degré moyen maximum moins de 5=2 admet un homomorphisme dans le graphe de Petersen. En outre, nous montrons que la borne sur le degré moyen maximum est la meilleure possible. / In this thesis, we are interested in various vertex coloring and homomorphism problems of graphs with special emphasis on planar graphs and sparsegraphs. We consider proper vertex coloring, acyclic coloring, star coloring, forestcoloring, fractional coloring and the list version of most of these concepts.In Chapter 2, we consider the problem of finding sufficient conditions for a planargraph to be 3-choosable. These conditions are expressed in terms of forbiddensubgraphs and our results extend several known results.The notion of acyclic list coloring of planar graphs was introduced by Borodin,Fon-Der Flaass, Kostochka, Raspaud, and Sopena. They conjectured that everyplanar graph is acyclically 5-choosable. In Chapter 3, we obtain some sufficientconditions for planar graphs to be acyclically k-choosable with k 2 f3; 4; 5g.In Chapter 4, we prove that every subcubic graph is 6-star-colorable. On theother hand, Fertin, Raspaud and Reed showed that the Wagner graph cannot be5-star-colorable. This fact implies that our result is best possible. Moreover, weobtain new upper bounds on star choosability of planar subcubic graphs with givengirth.A k-forest-coloring of a graph G is a mapping ¼ from V (G) to the set f1; ¢ ¢ ¢ ; kgsuch that each color class induces a forest. The vertex-arboricity of G is the smallestinteger k such that G has a k-forest-coloring. In Chapter 5, we prove a conjecture ofRaspaud and Wang asserting that every planar graph without intersecting triangleshas vertex-arboricity at most 2.Finally, in Chapter 6, we focus on the homomorphism problems of sparse graphsto the Petersen graph. More precisely, we prove that every triangle-free graph withmaximum average degree less than 5=2 admits a homomorphism to the Petersengraph. Moreover, we show that the bound on the maximum average degree in ourresult is best possible.