Dans cette thèse nous explorons différentes décompositions de graphes. Le titre de la présente thèse est dû au fait que la majorité de ces décompositions sont des décompositions voisin-distinguantes. En d'autres mots, nous pouvons en extraire des colorations propres des sommets. La question principale présentée dans cette thèse a été introduite par Karoński, Łuczak et Thomason: Est il possible de pondérer les arêtes d'un graphes avec les poids 1, 2 et 3, afin que tous les sommets voisins soient distingués par la somme des poids de leurs arêtes incidentes ? Cette question deviendra plus tard la fameuse 1-2-3 Conjecture. Nous présentons différentes variantes de la 1-2-3 Conjecture, ainsi que leurs liens avec les décompositions localement irrégulières. Nous nous intéressons tant à des problèmes d'optimisation qu'à des problèmes algorithmiques. Nous commençons par introduire une variante équitable des arête-pondérations voisin-somme-distinguantes, où chaque poids doit être utilisé le même nombre de fois (à l'unité près). Ensuite nous présentons une variante injective ou chaque poids est utilisé au plus une seule fois. Ce qui est un cas particulier de la variante équitable. De plus les pondérations injectives sont une variante locale des étiquetages anti-magiques. Ensuite nous modifions les conditions de distinction entre voisin en introduisant une variante 2-distinguante. les pondérations voisins-somme-2-distinguantes requierent que deux sommets voisins dans le graphe aient des sommes incidentes qui diffèrent d'au moins 2. Nous étudions le poids maximum minimal dans de telles pondérations pour certaines familles de graphes, ainsi que des problèmes de complexité. Dû aux liens entre les pondérations voisins-sommet-distinguantes et les décompositions localement irrégulières, nous nous sommes aussi intéressé à ces dernières, particulièrement pour les graphes sub-cubiques, ainsi qu'à d'autres variantes des décompositions localement irrégulières. Finalement nous présentons un jeu de pondérations à deux joueurs, ainsi qu'une théorie de décompositions qui unifie les pondérations voisin-somme-distinguantes et les décompositions localement irrégulières. / In this thesis we explore graph decompositions under different constraints. The title of the is due to the fact that most of these decompositions are neighbour-distinguishing. That is, we can extract from each such decomposition a proper vertex colouring. Moreover, most of the considered decompositions are edge partitions, and therefore can be seen as edge-colourings. The main question presented in this thesis is was introduced by Karoński, Łuczak and Thomason in [KLT04]: Can we weight the edges of a graph G, with weights 1, 2, and 3, such that any two of adjacent vertices of G are distinguished by the sum of their incident weights ? This question later becomes the famous 1-2-3 Conjecture. In this thesis we explore several variants of the 1-2-3 Conjecture, and their links with locally irregular decompositions. We are interested in both optimisation results and algorithmic problems. We first introduce an equitable version of the neighbour-sum- distinguishing edge-weightings, that is a variant where we require every edge weight to be used the same number of times up to a difference of 1. Then we explore an inject- ive variant where each edge is assigned a different weight, which yields necessarily an equitable weighting. This gives us first general upper bounds on the equitable version. Moreover, the injective variant is also a local version of the well-known antimagic la- belling. After that we explore how neighbour-sum-distinguishing weightings behave if we require sums of neighbouring vertices to differ by at least 2. Namely, we present results on the smallest maximal weight needed to construct such weightings for some classes of graphs, and study some algorithmic aspects of this problem. Due to the links between neighbour-sum-distinguishing edge weightings and locally irregular decompositions, we also explore the locally irregular index of subcubic graphs, along with other variants of the locally irregular decomposition problem. Finally, we present a more general work to- ward a general theory unifying nsd edge-weightings and locally irregular decompositions. We also present a 2-player game version of neighbour-sum-distinguishing edge-weightings and exhibit sufficient conditions for each player to win the game.

La première partie de cette thèse traite d'un problème de coloration dans les groupes finis. Pour une équation “régulière”, nous nous intéressons aux nombres de solutions différemment colorées. Nous montrons qu'il existe des combinaisons linéaires entre ces nombres de solutions, qui ne dépendent que des cardinaux des classes de couleurs et pas de leur répartition.<br />La seconde partie de cette thèse se place dans le contexte de la théorie additive des nombres. Nous développons une nouvelle approche de la méthode isopérimétrique de Y. ould Hamidoune, qui nous permet, entre autres, de donner une nouvelle démonstration du théorème de Kneser, outil majeur en théorie additive des nombres. Nous donnons une autre application de cette nouvelle approche à la détermination de nouvelles valeurs de taille minimale d'une somme de deux ensembles de tailles fixées, dans des groupes non abéliens. Ces nouvelles valeurs répondent par la négative à une question de la littérature.

Nous présentons d'abord les théorèmes du No Free Lunch en nous basant sur le papier de D.H. Wolpert et W.G. Macready (version IEEE 1997) mais aussi les multiples réactions que ces résultats ont provoquées dans la communauté de l'optimisation. Convaincus dès lors de l'intérêt d'une approche globale des problèmes et de la nécessité de la recherche de propriétés générales - et spécialement des invariances par symétries -, nous tentons ensuite de mettre en oeuvre cette méthode dans le cadre de la coloration de graphes simples et non orientés. Ce champ est retenu en raison de son intérêt propre, mais aussi pour son caractère de modèle fécond dans de multiples problèmes d'optimisation. Nous faisons émerger la notion de décomposition d'un graphe en cliques maximales et celle de suites constructives qui permettent de reconstruire un graphe à partir de ses composants élémentaires (primary cliques), véritables équivalents des nombres premiers pour les entiers naturels. Nous produisons un algorithme principal et en étudions deux cas singuliers; ensemble ils fournissent une partition de l'ensemble des colorations valides du graphe étudié. Par suite nous retrouvons le polynôme chromatique de manière formelle, indépendamment du nombre de couleurs disponibles. Nous établissons une correspondance de Galois entre colorations valides et sous-graphes engendrés par des familles emboîtées de cliques maximales pourvu qu'elles soient des décompositions complètes de sous-graphes croissants du graphe total.

Les codes identifiants ont été introduits en 1998 par Karpovsky, Chakrabarty et Levitin. Un code identifiant est un sous-graphe tel que chaque sommet est identifié de manière unique par les sommets du code qui l'entourent. Il existe plusieurs variantes de ces codes, dont notamment une version colorée dans laquelle les sommets sont identifiés par les couleurs dans leur voisinage. Dans cette thèse, nous cherchons en particulier à construire un cycle le plus grand possible qui admette une coloration identifiante, étant donné un nombre de couleurs fixé. Nous avons aussi étudié le problème des codes identifiants sur une classe particulière de graphes orientés : les tournois. Dans une seconde partie, nous avons aussi étudié deux jeux particuliers. Le premier est une généralisation des jeux octaux - qui se jouent normalement sur un tas - aux graphes. Plus précisemment, le jeu 0.33 ; chaque joueur peut retirer un ou deux sommets voisins d'un graphe, sans déconnecter ce dernier. Le premier qui ne peut plus jouer perd. Nous avons été capable de caractériser les issues de ce jeu dans des classes de graphes particulières, les étoiles subdivisées et les bi-étoiles subdivisées. Le second jeu est appelé le jeu du Pompier (Firefighter). Il consiste à arrêter un feu qui se propage dans un graphe en protégeant des sommets à chaque tour. Nous avons résolu une conjecture sur ce jeu, et introduit la version online, pour laquelle nous avons pu donner des résultats d'approximation. / Identifying codes were introduced in 1998 by Karpovsky, Chakrabarty and Levitin. An identifying code is a subgraph such that each vertex is uniquely identified by the vertices in its neighborhood. There are several variants of these codes, including a colored version where the vertices are identified by the colors in their neighborhood. In this phd, we want to build an identifying coloring of a large cycle, given a fixed number of colors. We also studied identified codes in a certain class of oriented graphs: tournaments. We have also studied some topics in the game theory. The first one is a generalization of octal games, where we play on a graph instead of a heap. More precisely, the 0.33 game; each player can remove one or two vertices in a graph, with no disconnection allowed. The first player who cannot play loses. We studied this game in some graph classes: subdivided stars and subdivided bistars. The other game is called the Firefighter game. It's a one player game, where this one wants to contain a spreading fire in a graph. We solved a conjecture about this game, and introduced the online version of the game, for which we found some approximation results.

Cette thèse se situe dans le domaine de graphes et de leurs applications, Elleest constitué de trois grandes parties, la première est consacrée à l’étude d’unnouveau type de coloration sommets distinguantes, les arête-colorations sommetsdistinguantespar écarte. Il consiste de trouver une valuation des arêtes qui permettede distinguer les sommets de graphes telle que chaque sommet v du graphe est identifiéde façon unique par la différence entre la plus grande et la plus petite des valeursincidentes à v. Le plus entier pour lequel le graphe G admet une arête-colorationsommets-distinguantes par écarte est le nombre chromatique par écart de G, notégap(G). Nous avons étudié ce paramètre pour diverses familles de graphes. Uneconjecture intéressante, proposée dans cette partie, suggère que le nombre chromatiquepar écart de tout graphe connexe d’ordre n > 2 vaut n - 1, n ou n + 1.La deuxième partie du manuscrit concerne le problème du placement de graphes.Nous proposons un état de l’art des problèmes de placement de graphes, puis nousintroduisons la nouvelle notion de placement de graphes étiquetés. Il s’agit d’unplacement de graphes qui préserve les étiquettes des sommets. Ensuite, nous proposonsdes encadrements de ce nouveau paramètre pour plusieurs classes de graphes.La troisième partie de la thèse s’intéresse au problème d’appariement d’arbres dansle cadre de la recherche d’information dans des documents structurés de type XML.Les algorithmes holistique de jointure structurelle est l’une des premières méthodesproposées pour résoudre l’appariement exact des documents XML. Ces algorithmessont souvent divisés en deux grandes étapes. La première étape permet de décomposerl’arbre de la requête en un ensemble de petites composantes connexes. Ensuite,des solutions intermédiaires pour chaque composante de la requête sont trouvées, cesrésultats intermédiaires sont joints pour obtenir la solution finale. Nous proposonsdans cette partie un nouvel algorithme appelé TwigStack++ qui vise principalementà diminuer le coût de la jointure et le calcule inutile recherche. Notre algorithmeobtient de meilleurs résultats en comparaison avec deux autres méthodes de l’étatde l’art. / In this thesis, we investigate some problems in graph theory, namelythe graph coloring problem, the graph packing problem and tree pattern matchingfor XML query processing. The common point between these problems is that theyuse labeled graphs.In the first part, we study a new coloring parameter of graphs called the gapvertex-distinguishing edge coloring. It consists in an edge-coloring of a graph G whichinduces a vertex distinguishing labeling of G such that the label of each vertex isgiven by the difference between the highest and the lowest colors of its adjacentedges. The minimum number of colors required for a gap vertex-distinguishing edgecoloring of G is called the gap chromatic number of G and is denoted by gap(G).We will compute this parameter for a large set of graphs G of order n and we evenprove that gap(G) 2 fn E 1; n; n + 1g.In the second part, we focus on graph packing problems, which is an area ofgraph theory that has grown significantly over the past several years. However, themajority of existing works focuses on unlabeled graphs. In this thesis, we introducefor the first time the packing problem for a vertex labeled graph. Roughly speaking,it consists of graph packing which preserves the labels of the vertices. We studythe corresponding optimization parameter on several classes of graphs, as well asfinding general bounds and characterizations.The last part deal with the query processing of a core subset of XML query languages:XML twig queries. An XML twig query, represented as a small query tree,is essentially a complex selection on the structure of an XML document. Matching atwig query means finding all the occurrences of the query tree embedded in the XMLdata tree. Many holistic twig join algorithms have been proposed to match XMLtwig pattern. Most of these algorithms find twig pattern matching in two steps. Inthe first one, a query tree is decomposed into smaller pieces, and solutions againstthese pieces are found. In the second step, all of these partial solutions are joinedtogether to generate the final solutions. In this part, we propose a novel holistictwig join algorithm, called TwigStack++, which features two main improvementsin the decomposition and matching phase. The proposed solutions are shown to beefficient and scalable, and should be helpful for the future research on efficient queryprocessing in a large XML database.

Dans cette thèse, nous nous intéressons à la résolution exacte de problèmes NP-difficiles sur les graphes et les hypergraphes. Les problèmes que nous étudions regroupent dans un premier temps des variantes du problème classique du nombre chromatique. Les variantes de ce problème se distinguent par la difficulté introduite par les relations entre les classes de couleurs, ou la difficulté de reconnaissance des classes de couleurs elles-mêmes. Puis nous ferons le lien avec les problèmes de transversaux sur les hypergraphes. Plus particulièrement, il s’agira de s’intéresser à l’énumération de transversaux minimaux dans un hypergraphe de rang borné. Outre la résolution exacte, nous nous intéressons à la résolution à paramètre fixe. Le problème de racine carrée de graphe est un problème important en théorie des graphes. Nous proposons et montrons la solubilité à paramètre fixe de deux problèmes d’optimisation reliés. Finalement, nous nous intéresserons à la résolution de problèmes de graphe, soit en lien avec les problèmes de colorations, soit pour montrer les performances possibles de différents algorithmes en fonction de l’espace mémoire disponible. Dans cette thèse, nous aurons à cœur d’appliquer judicieusement la grande majorité des techniques essentielles en algorithmique exacte exponentielle. Principalement, nous appliquerons la programmation dynamique ou le principe d’inclusion-exclusion pour les problèmes de coloration. La technique de programmation dynamique se retrouvera pour d’autres problèmes de cette thèse, aux côtés d’autres méthodes comme la technique de branchement ou de mesurer et conquérir / In this thesis, we are interested in the exact computation of np-hard problems on graphs and hypergraphs. Firstly, we study several variants of colorings. Those variants appear harder than the famous chromatic number problem, by adding difficulty in recognizing the color classes, or more often by introducing various relationships between them. Then we link to problems of transversals in hypergraphs. More precisely, we are interested in enumerating minimal transversals in bounded ranked hypergraphs. Besides the exact computation, we are also interested in fixed parameter tractability. For this area, we study two optimization versions of the famous square root of graphs problem. Finally, we will be interested in solving other problems of graphs related to colorings, or in order to compare efficiencies of algorithms depending on the memory space available. In this thesis, we will apply most of major techniques in designing exact exponential algorithms. The main techniques we use are dynamic programming, inclusion-exclusion, branching, or measure and conquer