Search

In this thesis, we consider two families of computational problems defined on graphs: proper edge-labellings and combinatorial games. We attack these problems in a similar (and classical) way: we show that they are computationally hard, and then find efficient algorithms for instances with specific structure.First we focus on problems related to proper labellings of graphs. For some natural number k, a k-labelling is a weight function on the edges of a graph G, assigning weights, called labels in this context, from {1, . . . , k}. A k-labelling induces a vertex-colouring of G, where each vertex receives as colour the sum of the labels of its incident edges. A k-labelling is proper if the induced vertex-colouring is proper, i.e., such that any two adjacent vertices of G are assigned different colours. According to the so-called 1-2-3 Conjecture, any connected graph of order at least 3 should admit a proper 3-labelling. We consider three variations of this conjecture. We look into equitable proper k-labellings, for which the assigned labels appear an equal number of times. We then focus on proper labellings that also minimise the sum of labels being used, and finally, proper 3-labellings that also minimise the number of times that the label 3 is assigned. The choice to study these variations is natural. Indeed, an equitable version of the 1-2-3 Conjecture claims that almost every graph G should admit an equitable proper 3-labelling. Also, the sum of labels of such a labelling would be at most 2|E(G)| and it would assign label 3 on at most one third of the edges of G. We prove that the introduced optimisation problems are NP-hard. Furthermore, through structural and algorithmical results, we propose new conjectures for the upper bounds of the parameters that we study, which we verify for specific graph classes (e.g. complete, bipartite, regular, 3-chromatic, etc.). Interestingly, our work gives further evidence that stronger variations of the 1-2-3 Conjecture could hold. We close our study of proper labellings by considering the problem of finding a largest induced subgraph of a given graph that admits a proper 1-labelling. This problem is proven to be computationally hard and not approximable within a ratio of O(|V (G)|^(1-1/c)) for every natural number c. Nevertheless, we provide efficient parameterised algorithms.In the second part of the thesis, we introduce and study the Maker-Breaker largest connected subgraph game. This game is played by two players, Alice and Bob, on a shared, initially uncoloured graph G. The two players take turns colouring the vertices of G, each one with their own colour, until there remains no uncoloured vertex. Alice is the winner of the game if, by the end, the largest connected subgraph of G induced by her colour is of order greater than k, where the natural number k is also given at the start of the game. Otherwise Bob wins the game. We also consider a Maker-Maker version of the same game, played in the same way, but in which the winner is the player whose colour induces the largest connected subgraph of G by the end of the game. We first prove that deciding the outcome of both of these games is PSPACE-hard, and then proceed by providing efficient algorithms when the games are played on particular graph classes (e.g. paths, cycles, cographs, (q, q-4)-graphs, etc.). Comparing the behaviour of these games, one of the main differences we observe is that Bob can never win the Maker-Maker version (if Alice plays optimally). Nevertheless, if Alice can win the Maker-Breaker version when playing on G for a value of k equal to half the order of G (the best outcome she can hopefor), then she can build a connected subgraph of the same order for the Maker-Maker version; such graphs are called A-perfect. We then study regular graphs that are A-perfect and prove that, surprisingly, any 3-regular A-perfect graph has order at most 132. We finish by providing sufficient conditions for a graph to be A-perfect.; Cette thèse considère deux familles de problèmes définis sur des graphes : les étiquetages d'arêtes propres et les jeux combinatoires. Nous traitons ces problèmes de façon similaire (et classique) : nous montrons que les problèmes considérés sont difficiles à résoudre, puis nous trouvons des algorithmes efficaces sur des instances restreintes.Nous nous concentrons d'abord sur des problèmes concernant des étiquetages propres de graphes. Pour un entier k fixé, un k-étiquetage d'un graphe G est une fonction associant à chaque arête de G une étiquette parmi {1, . . . , k}. Un k-étiquetage induit une coloration des sommets de G, où chaque sommet reçoit comme couleur la somme des étiquettes de ses arêtes incidentes. Un k-étiquetage est propre si, dans la coloration induite, deux sommets adjacents de G reçoivent des couleurs différentes. D'après la Conjecture 1-2-3, tout graphe connexe d'ordre au moins 3 admet un 3-étiquetage propre. Nous considérons trois variantes de cette conjecture. Nous étudions les k-étiquetages propres équilibrés, pour lesquels les étiquettes assignées apparaissent dans les mêmes proportions. La deuxième variante concerne les étiquetages propres qui minimisent la somme des étiquettes utilisées. Enfin, nous nous intéressons aux 3-étiquetages propres qui minimisent le nombre de fois où l'étiquette 3 est attribuée. Le choix d'étudier ces variantes est naturel. En effet, une version équilibrée de la Conjecture 1-2-3 est que presque tous les graphes G admettent un 3-étiquetage propre équilibré. En outre, la somme des étiquettes d'un tel étiquetage est au plus égale à 2|E(G)| et associe l'étiquette 3 à au plus un tiers des arêtes de G. Nous prouvons que les problèmes d'optimisation introduits sont NP-difficiles. Grâce à des résultats structurels et algorithmiques, nous sommes amenés à proposer de nouvelles conjectures pour ces problèmes, que nous vérifions sur quelques classes de graphes (complets, bipartis, réguliers, 3-chromatiques, etc.). Notre travail renforce l'idée que des variantes plus fortes de la Conjecture 1-2-3 pourraient être vraies. Nous terminons en considérant le problème consistant à trouver un plus grand sous-graphe induit d'un graphe donné qui admet un 1-étiquetage propre. Il est prouvé que ce problème est difficile à résoudre et qu'il n'est pas approximable à un facteur O(|V (G)|^(1-1/c)) près pour tout entier c. Néanmoins, nous fournissons des algorithmes paramétrés efficaces.La deuxième partie de la thèse introduit le jeu du plus grand sous-graphe connexe Maker-Breaker, joué par deux joueurs, Alice et Bob, sur un graphe G, initialement non coloré. Les joueurs colorent à tour de rôle les sommets de G, chacun avec sa couleur, jusqu'à ce que tous les sommets soient colorés. Alice est la gagnante si, à la fin, le plus grand sous-graphe connexe de G induit par sa couleur est d'ordre au moins k, un entier fixé. Sinon, Bob gagne le jeu. Nous considérons aussi une version Maker-Maker du même jeu, dans laquelle le gagnant est le joueur dont la couleur induit le plus grand sous-graphe connexe de G à la fin du jeu. Nous prouvons que décider de l'issue de ces deux jeux est PSPACE-difficile et nous fournissons des algorithmes efficaces pour le cas où le jeu se déroule dans certaines familles de graphes (chemins, cycles, cographes, (q, q-4)-graphes, etc.). En comparant ces deux jeux, la principale différence que nous observons est que Bob ne peut jamais gagner la version Maker-Maker (si Alice joue de manière optimale). Pour une valeur de k égale à la moitié de l'ordre de G, remarquons que si Alice peut gagner la version Maker-Breaker alors elle peut aussi construire un sous-graphe connexe du même ordre dans la version Maker-Maker ; de tels graphes sont nommés A-parfaits. Nous étudions les graphes réguliers qui sont A-parfaits et prouvons que tout graphe 3-régulier A-parfait a au plus 132 sommets. Nous terminons en fournissant des conditions suffisantes pour qu'un graphe soit A-parfait.

International audience; Dans le jeu du plus grand sous-graphe connexe, deux joueurs, Anaïs et Gilles, s'affrontent en colorant les sommets d'un graphe. À chaque tour, Anaïs colore un sommet non coloré en rouge puis Gilles colore un sommet non coloré en bleu. Lorsque tous les sommets sont colorés, le joueur dont la couleur induit la plus grande composante connexe gagne. Ce jeu a été défini dans [Bensmail et al, WG'21 et AlgoTel'21] où il a été montré entre autres que Gilles n'a jamais de stratégie gagnante (au mieux, il peut espérer une égalité). Nous étudions la version de ce jeu où on se donne aussi un entier $k\geq 1$. Dans ce cas, Anaïs gagne si elle crée une composante connexe rouge de taille au moins k et Gilles gagne sinon. Étant donné un graphe $G$, nous étudions $c_g(G)$, le plus grand entier qui garantit la victoire d'Anaïs. Outre le fait que cela donne une chance à Gilles de gagner, cette variante fait partie de la famille des jeux combinatoires Maker-Breaker, qui ont été très étudiés. De plus, cette variante offre des outils différents pour mieux comprendre la version Maker-Maker initiale. En particulier, nous étudions les graphes A-parfaits pour lesquels Anaïs peut gagner en créant une unique composante rouge, i.e., les graphes à n sommets tels que $c_g(G) = \lceil n/2 \rceil$. Nous montrons que le calcul de $c_g(G)$ est PSPACE-complet dans les graphes bipartis, scindés (split) ou planaires, et que et une stratégie correspondante peuvent être calculés en temps linéaire dans les graphes $P_4$-clairsemés (généralisant les cographes). Nous donnons ensuite des conditions suffisantes (liées aux degrés ou au nombre d'arêtes) pour qu'un graphe soit A-parfait. Un résultat surprenant est qu'il n'existe aucun graphe 3-régulier A-parfait avec plus de 132 sommets.

International audience; This paper introduces the largest connected subgraph game played on an undirected graph G.In each round, Alice first colours an uncoloured vertex of G red, and then, Bob colours an uncoloured vertex of G blue, with all vertices initially uncoloured. Once all the vertices are coloured, Alice (Bob, resp.) wins if there is a red (blue, resp.) connected subgraph whose order is greater than the order of any blue (red, resp.) connected subgraph. We first prove that Bob can never win, and define a large class of graphs (called reflection graphs) in which the game is a draw. We then show that determining the outcome of the game is PSPACE-complete, even in bipartite graphs of small diameter, and that recognising reflection graphs is GI-hard. We also prove that the game is a draw in paths if and only if the path is of even order or has at least 11 vertices, and that Alice wins in cycles if and only if the cycle is of odd length. Lastly, we give an algorithm to determine the outcome of the game in cographs in linear time.; Nous définissons le jeu du plus grand sous-graphe connexe. Soit un graphe dont les sommets sont initialement non colorés. Tour-à-tour, le premier joueur, Alice, colore en rouge un sommet non coloré, puis le second joueur, Bob, colore un sommet non coloré en bleu, et ainsi de suite. Le jeu s'achève lorsque tous les sommets du graphe ont été colorés. Le vainqueur est le joueur dont le sous-graphe coloré a la plus grande composante connexe. Nous prouvons que, si Alice joue optimalement, Bob ne peut jamais gagner, et définissons une classe de graphes infinie, appelés graphes miroirs, dans lesquels Bob peut forcer une égalité. Du point de vue complexité, nous montrons ensuite que déterminer l'issue du jeu est PSPACE-complet même lorsque restreint aux graphes bipartis de petit diamètre, et que reconnaître un graphe miroir est GI-difficile. Enfin, nous caractérisons les chemins et cycles dans lesquels Alice gagne et nous prouvons que l’issue du jeu peut être déterminée en temps linéaire dans la classe des cographes.

Given a graph $G$ and an integer $k \in \mathbb{N}$, we introduce the following Maker-Breaker game played in $G$. Each round, first Alice colours an uncoloured vertex of $G$ red, and then Bob colours an uncoloured vertex blue (if any remain). Once all the vertices have been coloured, Alice wins if there exists a connected red component of order at least $k$, and if not, then Bob wins. This game is a Maker-Breaker version of the Largest Connected Subgraph game introduced in [Bensmail, Fioravantes, Mc Inerney, and Nisse, WG 2021]. We are interested in computing $c_g(G)$, which is the maximum $k$ such that Alice wins in $G$, regardless of what Bob does.Given a graph $G$ and an integer $k\geq 1$, we prove that deciding whether $c_g(G)\geq k$ is PSPACE-complete, even if $G$ is restricted to be in the class of bipartite graphs of diameter~$4$, split graphs, or planar graphs. Then, we focus on {\it A-perfect} graphs, namely, graphs for which $c_g(G)=\left \lceil \frac{|V(G)|}{2}\right \rceil$, {\it i.e.}, the maximum possible value. We show that there exist arbitrarily large A-perfect $d$-regular graphs for any $d \geq 4$, but, surprisingly, that no cubic graph with order at least $133$ is A-perfect. Moreover, we give sufficient conditions, in terms of the number of edges or the maximum and minimum degree, for a graph to be A-perfect.Finally, we show that $c_g(G)$ can be computed in polynomial time when $G$ is a $P_4$-sparse graph (a superclass of cographs). We conclude with many open questions. In particular, natural graph classes such as trees and grid-like graphs seem to be difficult to deal with. We only give partial results in the case of some grid-like graphs.

In this work, we consider equitable proper labellings of graphs, which were recently introduced by Baudon, Pilśniak, Przybyƚo, Senhaji, Sopena, and Wozńiak. Given a graph G, the goal is to assign labels to the edges so that 1) no two adjacent vertices are incident to the same sum of labels, and 2) every two labels are assigned about the same number of times. Particularly , we aim at designing such equitable proper k-labellings of G with k being as small as possible. In connection with the so-called 1-2-3 Conjecture, it might be that labels 1,2,3 are, a few obvious exceptions apart, always sufficient to achieve this just as in the non-equitable version of the problem. We provide results regarding some open questions about equitable proper labellings. Via a hardness result, we first prove that there exist infinitely many graphs for which more labels are required in the equitable version than in the non-equitable version. This remains true in the bipartite case. We finally show that, for every $k≥3$, every k-regular bipartite graph admits an equitable proper k-labelling.