A coalition in a graph G =(V, E) consists of two disjoint sets of vertices V1 and V2, neither of which is a dominating set of G but whose union V1 ∪ V2 is a dominating set of G.A coalition partition in a graph G of order n = |V| is a vertex partition π= {V1, V2,⋯, Vk} of V such that every set Vi either is a dominating set consisting of a single vertex of degree n - 1, or is not a dominating set but forms a coalition with another set Vj which is not a dominating set. Associated with every coalition partition πof a graph G is a graph called the coalition graph of G with respect to π, denoted CG(G, π), the vertices of which correspond one-to-one with the sets V1, V2,⋯, Vk of πand two vertices are adjacent in CG(G, π) if and only if their corresponding sets in πform a coalition. In this paper we study coalition graphs, focusing on the coalition graphs of paths, cycles, and trees. We show that there are only finitely many coalition graphs of paths and finitely many coalition graphs of cycles and we identify precisely what they are. On the other hand, we show that there are infinitely many coalition graphs of trees and characterize this family of graphs.

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.

The study and recognition of graph families (or graph properties) is an essential part of combinatorics. Graph colouring is another fundamental concept of graph theory that can be looked at, in large part, as the recognition of a family of graphs that are colourable according to certain rules. In this thesis, we study additive induced-hereditary families, and some generalisations, from a colouring perspective. Our main results are: · Additive induced-hereditary families are uniquely factorisable into irreducible families. · If <i>P</i> and <i>Q</i> are additive induced-hereditary graph families, then (<i>P</i>,<i>Q</i>)-COLOURING is NP-hard, with the exception of GRAPH 2-COLOURING. Moreover, with the same exception, (<i>P</i>,<i>Q</i>)-COLOURING is NP-complete iff <i>P</i>- and <i>Q</i>-RECOGNITION are both in NP. This proves a 1997 conjecture of Kratochvíl and Schiermeyer. We also provide generalisations to somewhat larger families. Other results that we prove include: · a characterisation of the minimal forbidden subgraphs of a hereditary property in terms of its minimal forbidden induced-subgraphs, and <i>vice versa</i>; · extensions of Mihók's construction of uniquely colourable graphs, and Scheinerman's characterisations of compositivity, to disjoint compositive properties; · an induced-hereditary property has at least two factorisations into arbitrary irreducible properties, with an explicitly described set of exceptions; · if <i>G</i> is a generating set for <i>A</i> &#959; <i>B</i>, where <i>A</i> and <i>B</i> are indiscompositive, then we can extract generating sets for <i>A</i> and <i>B</i> using a <i>greedy algorithm</i>.

The study and recognition of graph families (or graph properties) is an essential part of combinatorics. Graph colouring is another fundamental concept of graph theory that can be looked at, in large part, as the recognition of a family of graphs that are colourable according to certain rules. In this thesis, we study additive induced-hereditary families, and some generalisations, from a colouring perspective. Our main results are: · Additive induced-hereditary families are uniquely factorisable into irreducible families. · If <i>P</i> and <i>Q</i> are additive induced-hereditary graph families, then (<i>P</i>,<i>Q</i>)-COLOURING is NP-hard, with the exception of GRAPH 2-COLOURING. Moreover, with the same exception, (<i>P</i>,<i>Q</i>)-COLOURING is NP-complete iff <i>P</i>- and <i>Q</i>-RECOGNITION are both in NP. This proves a 1997 conjecture of Kratochvíl and Schiermeyer. We also provide generalisations to somewhat larger families. Other results that we prove include: · a characterisation of the minimal forbidden subgraphs of a hereditary property in terms of its minimal forbidden induced-subgraphs, and <i>vice versa</i>; · extensions of Mihók's construction of uniquely colourable graphs, and Scheinerman's characterisations of compositivity, to disjoint compositive properties; · an induced-hereditary property has at least two factorisations into arbitrary irreducible properties, with an explicitly described set of exceptions; · if <i>G</i> is a generating set for <i>A</i> &#959; <i>B</i>, where <i>A</i> and <i>B</i> are indiscompositive, then we can extract generating sets for <i>A</i> and <i>B</i> using a <i>greedy algorithm</i>.