Distinguantes De Graphes

Julien Bensmail

Mickaël Montassier

Olivier Togni

Cristina Bazgan

Frédéric Cazals

CONTRIBUTIONS AUX PONDÉRATIONS

Keywords: distinguishing labellings, 1-2-3 Conjecture, locally irregular decompositions, graph decompositions, graph colourings pondérations distinguantes, 1-2-3 Conjecture, décompositions localement irrégulières, décompositions de graphes, colorations

This document describes some of the research work I have been conducting since the defence of my Ph.D. thesis at Université de Bordeaux, France, back in June 2014. It is more particularly focused on my contribution to distinguishing labellings of graphs, and the socalled 1-2-3 Conjecture that occupies an important place in this field. The general objective in this kind of problems is, given a (connected undirected) graph, to weight its edges in such a way that the adjacent vertices get distinguishable accordingly to some parameter computed from the edge-weighting. For instance, in the 1-2-3 Conjecture, raised by Karoński, Łuczak and Thomason in 2004, the aim is to weight the edges with 1, 2, 3 so that adjacent vertices get distinguished accordingly to their sums of incident weights.

Although the 1-2-3 Conjecture was raised as nothing but a toy problem when it was introduced, several results in the recent years have established its deeper nature. The conjecture, by its very definition, has undoubtedly an algebraic nature. Some results have also established that it has some decompositional flavour. Although the conjecture is rather artificial, it is also related to other classical notions of graph theory, such as proper vertex-colourings of graphs.

In this document, we focus on contributions to distinguishing labellings that stand as support to these points. This is done through two main chapters:

• In the first chapter, we present results related to several aspects of the 1-2-3 Conjecture.

The presented results are both on main aspects of the conjecture, i.e., that stand as evidence towards the main open questions related to it, and on more side aspects, i.e., that are helpful towards understanding better its general behaviour and mechanisms. These side aspects cover natural questions regarding the true importance of all weights 1, 2, 3 for the 1-2-3 Conjecture, the impact of requiring adjacent vertices to be "even more distinguishable", and generalisations of the conjecture to digraphs.

• In the second chapter, we present results on so-called locally irregular decompositions of graphs, which are a kind of decompositions attesting the very decompositional nature of the 1-2-3 Conjecture. The presented results include better decomposition results for graphs in general, as well as a general theory that is the key for relating locally irregular decompositions and the 1-2-3 Conjecture.

Each chapter comes up with a concluding section describing consequences of the presented results on the field, as well as perspectives for research we have for the near future.

Chapter 1

Introduction to the document

The current document describes some of the research I have been conducting since the defence of my Ph.D. thesis, done at LaBRI (Laboratoire Bordelais de Recherche en Informatique), Université de Bordeaux, France, from October 2011 to August 2014. The presented results were obtained during the successive positions I have occupied since then, namely as an "ATER" (postdoctoral position with teaching duties) at LIP (Laboratoire de l'Informatique du Parallélisme), École Normale Supérieure de Lyon, France, from September 2014 to August 2015, as a postdoctoral researcher at DTU (Technical University of Denmark), from September 2015 to August 2016, and as a "maître de conférences" (assistant professor) at I3S (Laboratoire d'Informatique, Signaux et Systèmes de Sophia Antipolis) and INRIA (Institut National de Recherche en Informatique et en Automatique), Université Côte d'Azur, France, since September 2016. These results were obtained through scientific collaborations with both students and more renowned scientists, from different countries and having different backgrounds.

This chapter serves as an introduction to the whole document.

• In Section 1.1, I start by having a look back at my research career up to the current point.

In particular, in that section, I describe how my approach to research has been evolving through the years. There, a special emphasise is put onto my main scientific contributions and achievements to date.

• A more specific focus on my main research theme, that of distinguishing labellings, which is to be developed throughout this document, is then given in Section 1.2. In that section, I do my best to describe why I think this field is of interest, and why it has been occupying a lot of my daily scientific work.

• I finish off in Section 1.3 by detailing the contents of the current document.

Description of my research career Successive positions and experiences

My research is mostly in graph theory. My very first steps into this mathematical field were made during my university studies at Université de Bordeaux, France, during which I got the chance to follow four courses on the topic. I first discovered the topic in 2007-2008 during the second year of my "DUT Informatique" (two-year French university degree), which was taught by Éric Sopena, who would coincidently become my Ph.D. supervisor later on. As far as I remember (sorry Éric ), the topic of this course was some basics of graph theory, covering, in particular, graph colouring. During the next year, 2008-2009, as part of my third university year, I then followed a course taught by André Raspaud, which was more on algorithmic graph theory. Two years later, during my fifth and last university year 2010-2011, I then followed a course on graph grammars taught by Bruno Courcelle, and a course on advanced graph theory taught by Ralf Klasing, Mickaël Montassier and, again, Éric Sopena. I keep very good memories of these courses, which were taught by people who were clearly passionate about graph theory. I have absolutely no doubt that this is the main reason why, when choosing a topic for my end-of-studies internship, I turned to that one. I then chose to still today, the most important ones I got to contribute to. Another nice aspect of my year in Lyon is that I was given the opportunity to supervise two smart students from ÉNS, Emma Barme and Khang Le, with whom we got very nice results, some of which I present in Chapter 2.

Right after my year in Lyon, I got the incredible chance to hold a postdoctoral position at DTU, Denmark, in the group of Carsten Thomassen. This was a very nice opportunity for many reasons, including the chance to spend time abroad, and, last but not least, to work with Carsten Thomassen, who can undoubtedly be regarded as one of the most prominent figures of graph theory. I got the chance to observe his very particular and simple approach to research, in particular at the occasion of some work we did together with Martin Merker, which resulted in a very nice result on a seemingly complicated problem, which is to be presented in Chapter 3. I also got to work with external collaborators, such as Binlong Li and Alan Arroyo. With the latter, we worked on pseudolinear drawings of graphs, which resulted in a nice result which was my first occasion to work on geometrical aspects of graph theory.

Since my arrival in Nice in 2016, my research has been staying in the line of that so far, as I have been trying my best to maintain my collaborations with some of the people above as far as I can. In particular, I still have regular connections with the groups of Éric Sopena, Jakub Przybyło and Carsten Thomassen. Due to collaborations in my current group, COATI, in particular with Nicolas Nisse, my research now tend to have a more algorithmic flavour, as we get to work on more operational research problems, such as problems inspired by industrial ones. We have also been interested in metric problems in graphs, such as ones related to the metric dimension problem, which we have been working on in the recent years. I also get the chance to benefit from long-term collaborations that were initiated before my venue here, such as with the group of Julio Araujo (Universidade Federal do Ceará, Fortaleza, Brazil), and with Chinese collaborators, Bi Li and Binlong Li, both located in Xi'an, China, whom Nicolas Nisse and I share as collaborators as a nice coincidence.

Scientific contributions to date

Having a look back at my scientific contribution up to this point, I would describe it as a combination of combinatorial, algorithmic and structural results on several colouring, decomposition and partition problems of graph theory. I enjoy working on seemingly unrelated problems, regardless of whether they admit practical applications. I am always willing to discover more and more problems and tools, to improve my general knowledge of graph theory. Another aspect I observe is that, though I have papers where I am the sole author, collaborations are important to me, especially with younger researchers.

To date, my most important contribution to graph theory is a series of two results on the Barát-Thomassen Conjecture obtained jointly with Harutyunyan, Le, Merker and Thomassé in [START_REF] Bensmail | A proof of the Barát-Thomassen conjecture[END_REF][START_REF] Bensmail | Edge-partitioning a graph into paths: beyond the Barát-Thomassen conjecture[END_REF]. This conjecture, stated in 2006 by Barát and Thomassen in [START_REF] Barát | Claw-decompositions and Tutte-orientations[END_REF], says that for every tree T there should exist a constant c T such that every c T -edge-connected graph with size divisible by |E(T )| admits a partition of its edge set where each part induces a copy of T . When we started working on the topic, this conjecture was only proved for a few trees T , such as paths and trees with diameter at most 4. In [START_REF] Bensmail | A proof of the Barát-Thomassen conjecture[END_REF], using a probabilistic approach, we managed to fully prove the Barát-Thomassen Conjecture for every tree T . In [START_REF] Bensmail | Edge-partitioning a graph into paths: beyond the Barát-Thomassen conjecture[END_REF], we also went beyond the Barát-Thomassen Conjecture by proving that when T is a path, decompositions into copies of T exist in graphs being mildly edge-connected but having large enough minimum degree.

My other most important series of scientific contributions are the following:

• Contributions to distinguishing labellings and the 1-2-3 Conjecture, which are precisely the topic of the current document.

• Contibutions to strong edge-colouring of graphs and the related Erdős-Nešetřil Conjecture with Harutyunyan, Hocquard, Lagoutte and Valicov in [START_REF] Bensmail | Strong edge-colouring of sparse planar graphs[END_REF][START_REF] Bensmail | Strong edge-coloring of (3, ∆)-bipartite graphs[END_REF]. That conjecture asserts that every graph with maximum degree ∆ should have a strong edge-colouring (i.e., 1.2. Main focus in this document an edge-colouring where every two edges at distance at most 2 receive distinct colours) with at most 5 4 ∆ 2 colours. To date, this conjecture has been verified for a few classes of graphs only. In [START_REF] Bensmail | Strong edge-coloring of (3, ∆)-bipartite graphs[END_REF], we provided a nice new approach for showing the conjecture for some bipartite graphs, for which, in general, the conjecture is still open. In [START_REF] Bensmail | Strong edge-colouring of sparse planar graphs[END_REF], we provided improved bounds for classes of planar graphs, which are among the most studied classes of graphs in this context.

• Contributions to partitioning graphs into connected subgraphs with Baudon, Foucaud, Kalinowski, Marczyk, Li, Pilśniak, Przybyło, Woźniak and Sopena in [START_REF] Baudon | Structural properties of recursively partitionable graphs with connectivity 2[END_REF][START_REF] Baudon | On the Cartesian product of an arbitrarily partitionable graph and a traceable graph[END_REF][START_REF] Baudon | Partitioning powers of traceable or Hamiltonian graphs[END_REF][START_REF] Baudon | Partitioning Harary graphs into connected subgraphs containing prescribed vertices[END_REF][START_REF] Bensmail | On the complexity of partitioning a graph into a few connected subgraphs[END_REF][START_REF] Bensmail | On three polynomial kernels of sequences for arbitrarily partitionable graphs[END_REF][START_REF] Bensmail | More Aspects of Arbitrarily Partitionable Graphs[END_REF]. In particular, we have investigated several properties of so-called arbitrarily partitionable graphs, which are graphs that can be partitioned into connected subgraphs in every possible manner, i.e., no matter how many such subgraphs are requested, and no matter what their orders are. We have particularly exhibited structural properties of these graphs (and some variants), and algorithmic results on their recognition. An interesting question here, is whether recognising arbitrarily partitionable graphs is a hard problem for some complexity class, and even whether this problem is in NP at all. Some of our results in the references above are towards that very question.

• Contributions to the proper vertex-colouring of decorated graphs with Das, Duvignau, Duffy, Kirgizov, Paul, Pierron, Nandi, Sen and Sopena in [START_REF] Bensmail | On the 2-edge-coloured chromatic number of grids[END_REF][START_REF] Bensmail | Pushable chromatic number of graphs with degree constraints[END_REF][START_REF] Bensmail | Analogues of cliques for (m, n)-colored mixed graphs[END_REF][START_REF] Bensmail | The complexity of deciding whether a graph admits an orientation with fixed weak diameter[END_REF][START_REF] Bensmail | On oriented cliques with respect to push operation[END_REF]. By "decorated graphs", it is here meant oriented graphs and 2-edge-coloured graphs, for which the notion of chromatic number is defined through homomorphisms. In the works above, we have studied generalisations of the classical theory of graph colouring to the realm of decorated graphs. In particular, we have studied generalisations of classical problems, such as the Four-Colour Conjecture, in this different context.

Others of my contributions of importance include results on list colouring of digraphs with Harutyunyan and Le in [START_REF] Bensmail | List coloring digraphs[END_REF], on disjoint cycles in digraphs and the related Bermond-Thomassen Conjecture with Harutyunyan, Le, Li and Lichiardopol in [START_REF] Bensmail | Disjoint cycles of different lengths in graphs and digraphs[END_REF], on pseudolinear drawings of graphs with Arroyo and Richter in [START_REF] Arroyo | Extending Drawings of Graphs to Arrangements of Pseudolines[END_REF], and on the metric dimension of graphs with Mazauric, Mc Inerney, Nisse and Pérennes in [START_REF] Bensmail | Sequential Metric Dimension[END_REF][START_REF] Bensmail | Metric Dimension: from Graphs to Oriented Graphs[END_REF].

Main focus in this document

One particular problem has been occupying a growing part of my daily scientific work. This problem is known as the 1-2-3 Conjecture nowadays. Although my strongest scientific achievements to date are not related to this problem, most of the results I am the most proud of relate to it. I think that most researchers have a special problem that will haunt them during their whole career, and that very one might just be mine. It has such a special flavour that it was impossible to me not dedicating this document to it. The same occurred to my Ph.D. thesis: Although the 1-2-3 Conjecture was not meant to be part of it, it eventually ended up occupying more than half of the document.

After so much teasing, let me introduce this intriguing 1-2-3 Conjecture. It reads as follows:

"For every connected graph different from K 2 , can we weight its edges with 1,2,3 so that no two adjacent vertices are incident to the same sum of weights?"

Many aspects behind this conjecture are remarkable. In particular, it is one of these numerous intriguing open problems of graph theory (and, more generally, of discrete mathematics) that can easily be stated, and that can be understood even by people without a strong mathematical background. It can just be stated as a game, where anyone can draw an arbitrary graph, and try to come up with a counterexample. Someone with more mathematical background will more likely be, at first glance, quite sceptical about the 1-2-3 Conjecture. There are so many graphs out there, with so many different behaviours and properties; For what reason should any graph be weightable in such a restrictive way? It would not have been surprising that every graph G can be weighted in such a way with weights 1, . . . , f (G) for some f (G) being dependent on some structural property or parameter of G. But using 1, 2, 3 only for every graph? There is definitely some magic in there.

The 1-2-3 Conjecture was introduced in [START_REF] Karoński | Edge weights and vertex colours[END_REF] by [START_REF] Karoński | Edge weights and vertex colours[END_REF]. A surprising fact to mention, is that, in that seminal work, the authors just state and study the conjecture right away, without providing any motivation for considering it. This is quite shameful, as, as I have been discovering over the years, this conjecture, despite its weirdness, actually has a place in graph theory that is not as isolated as one could think. In particular, the 1-2-3 Conjecture is part of the wide area of distinguishing labellings, a topic which, as reported by Gallian in [START_REF] Gallian | A dynamic survey of graph labeling[END_REF], is a quite prolific one, with more than 2600 papers dedicated to it in literature. The 1-2-3 Conjecture also has many interesting connections to more or less known notions of graph theory, such as proper vertex-colourings, locally irregular graphs, and so on. In our works on the subject, with my co-authors we have thus been putting lots of efforts into motivating the study of the 1-2-3 Conjecture and some of its aspects. Most of these interesting arguments are reported in the current document.

Although the 1-2-3 Conjecture was introduced over 15 years ago, there is actually only little known about it. In particular, it is only known to hold for a limited number of graph classes. Mentioning that the conjecture was verified for complete graphs and 3-colourable graphs is already almost the full picture of the verified graph classes. The conjecture was of course also verified for a number of other restricted classes of graphs, but nothing as significant. Stated this way, this sounds deceiving. Especially when adding that the proofs of the 1-2-3 Conjecture for complete graphs and 3-colourable graphs are, although invoking nice arguments, rather easy. And that these proofs were given right after the introduction of the 1-2-3 Conjecture.

So what has been on over these 15 years? Is there any point dedicating the current document to a conjecture with such little progress? Well, it turns out that the investigations are far from being dead, as there are many interesting aspects to consider, other than actually proving the 1-2-3 Conjecture. To date, the most efforts have been put on proving that weights 1, . . . , k work for graphs in general, for some k ≥ 3. And quite some improvements were made, starting from a proof that there is a set of 183 numbers (actually real numbers) working for all graphs, all the way down, though successive improvements, to a proof that weights 1, 2, 3, 4, 5 work for all graphs. An interesting point is the way the arguments have been refined over the years, as 1.3. Contents and organisation of the document they first involved probabilistic tools, before including rather intricate partition and degreeconstrained subgraph notions, and eventually switching to an elegant and simple algorithmic proof. It has to be emphasised that, in general, the 1-2-3 Conjecture requires innovative arguments for proving results; in particular, this is a problem that, by its very nature, is rather resistant to the usual inductive approaches that we like to use in discrete mathematics.

There are tons of other interesting aspects that the 1-2-3 Conjecture has to offer, which arise from its very nature. For instance, are all weights 1, 2, 3 really needed for almost all graphs? If yes, then when is weight 3 necessary? If weight 3 is sometimes needed, then must it be used a lot? And why 1, 2, 3 in the first place? Why not asking the same questions for any three pairwise distinct weights a, b, c? What can be said in general about the sums obtained through an edge-weighting? How can this problem be generalised? etc. While some of these questions are standard business in graph theory, some others are dealing with what is truly hiding behind the 1-2-3 Conjecture. Even if the conjecture was to be proved soon, some aspects would remain unclear, and, in my opinion, it would still make sense continuing investigating it.

Contents and organisation of the document

In connection with the arguments given in the previous section, my main goal in this document is thus to gather aspects and results related to the 1-2-3 Conjecture (and more generally distinguishing labellings) which I think make the problem interesting. As mentioned earlier, one of my concerns is to motivate these aspects as much as possible, notably by establishing some connections with other notions of graph theory. The problems and results I have selected for presentation form, thereby, a mixture that is, in my opinion, rather representative of those aspects I like to investigate in my research work. Although most of my results here are of combinatorial nature, many of them also have a more algorithmic nature, as algorithmic aspects tend to have a growing importance in my work. I also want to stress out that computer tools are having a more and more important place in my approach to research. A perfect illustration of this is that I was 100% confident that Conjecture 2.36 was false, before managing to prove it under the adequate statement (Theorem 2.37), which was suggested by a computer approach.

Another important point I want to mention, is that most of the results presented in this document result from collaborations involving students, of both undergraduate and graduate levels. For instance, the really nice arguments used to prove Theorem 2.33 were found as I was supervising an undergraduate student for an internship. Similarly, the results from Section 3.2, which I find really elegant and are definitely the nicest contribution in this document, were obtained mainly together with a Ph.D. student. For some reason, I tend to prefer and enjoy more doing research with students, and one of the source of pride I have today is presenting, in the current document, results and directions considered with some of them.

Before proceeding with presenting the organisation of the current document, let me raise a few introductory remarks first. I am assuming that the reader is familiar with at least the basics of graph theory and algorithmics. For this reason, no section dedicated to recalling the standard notions, definitions and terminology is to be found in the document. However, some non-standard notions, definitions and terminology can be found here and there throughout the document, either in one of the introductory sections or right before they are first employed. In case any such supposed standard notion, definition or terminology is unclear, I would refer the reader to standard monographs, such as [START_REF] Diestel | Graph Theory[END_REF] for graph theory, [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF] for algorithmic theory, [START_REF] Flajolet | Analytic combinatorics[END_REF] for combinatorics in general, and [START_REF] Alon | The Probabilistic Method[END_REF] for the probabilistic method, where the unclear thing has high chances to be defined properly.

Each of the two main chapters in this document is organised the same way. At the very beginning of each chapter, we start by a very vague description of the chapter's contents. We then give a general introduction to the chapter's topic, covering the needed notions and terminology, our motivations for studying the topic, and previous works that are relevant for understanding the place of the presented results in the literature. It is important to keep in mind that, here, we survey the field as it was before the presented investigations. Hence, the pictures depicted there are outdated now. The next sections are then dedicated to describing some of my contributions to the topic. At the beginning of each such section are mentioned the persons with whom the results were obtained, and the references of literature where these results can be found. Each chapter ends with a conclusion in which we describe how the chapter's topic has been evolving (if it has) since the presented results were obtained, and some scientific perspectives we have for the future. In particular, some of my contributions of lesser importance are mentioned there. Also, I do my very best so that, there, the depicted picture of the field is to date as accurately as possible.

This document is organised as follows. We start off in Chapter 2 by focusing on the 1-2-3 Conjecture. In that chapter, we first start with a deeper and more thorough introduction to this problem, including motivating aspects as well as previous results. Two series of contributions are then presented, namely contributions to main aspects of the 1-2-3 Conjecture in Section 2.2, and contributions to side aspects in Section 2.3. In Chapter 3, we then turn our intention to locally irregular decompositions of graphs, which are the key for comprehending the decompositional nature of the 1-2-3 Conjecture. A general conclusion to the document is eventually given in Chapter 4.

Chapter 2

1-2-3 Conjecture

Inthischapter,Idescribesomeofmyresearchworkrelatedtoneighbour-sum-distinguishing edge-weightings and the so-called 1-2-3 Conjecture. This conjecture, which was introduced in [START_REF] Karoński | Edge weights and vertex colours[END_REF] by Karoński, Łuczak and Thomason in 2004, is a truly intriguing one being part of these numerous complicated problems that admit an outstandingly easy formulation. It was originally introduced as nothing but a toy problem. Over the years, I however got to discover that the very nature of this conjecture is actually much deeper than one could originally think. The results presented in this chapter are then intended to illustrate some possible directions of interest, and the different arguments they can lead us to consider.

We start off in Section 2.1 by surveying aspects of the 1-2-3 Conjecture that connect to my work in some way. My goal here is not to survey the whole topic in an exhaustive way; in particular, I voluntarily omit some interesting works because they would not have a perfect fit in the global picture I am establishing. I would strongly recommend the interested reader to keep the reference [START_REF] Seamone | The 1-2-3 Conjecture and related problems: a survey[END_REF] in mind, which is a survey on the topic by Seamone in which most of the aspects missing from the current document are mentioned.

The rest of the chapter is then divided into two main sections, Sections 2.2 and 2.3, in which are presented some of my contributions to the field. Section 2.2 is dedicated to results on main aspects of the 1-2-3 Conjecture; by that, I mean results on some topics and questions that are trendy in the context. Two series of results are presented there, namely:

• In Section 2.2.1, a 1-2-3-4 result for 5-regular graphs, improving, for these graphs, the best result towards the 1-2-3 Conjecture. The most interesting aspect behind that result is the method we employ, which is by enhancing known tools with additional features.

• In Section 2.2.2, a study of 2-connected bipartite graphs that cannot be weighted in a particular way with two weights. This study partly answers some open questions of Thomassen, Wu and Zhang in [START_REF] Thomassen | The 3-flow conjecture, factors modulo k, and the 1-2-3-conjecture[END_REF], which is an important reference of the field.

In Section 2.3, we then describe results related to side aspects of the 1-2-3 Conjecture, i.e., aspects that are less central but are, I think, legitimate to wonder when having good general knowledge of the field. Three series of results are presented there:

• In Section 2.3.1 are presented results related to the true connection between neighboursum-distinguishing edge-weightings and proper vertex-colourings of graphs.

• In Section 2.3.2 we investigate the effects on the 1-2-3 Conjecture of requiring adjacent vertices to be "strongly distinguished" by an edge-weighting.

• In Section 2.3.3, we then investigate ways for generalising the 1-2-3 Conjecture for digraphs, and several results on that very aspect.

Introduction

Motivations and formal definitions

Before introducing the formal definitions and notions that will allow us to properly define the 1-2-3 Conjecture, let us first give some motivation to ease the whole introduction. The motivations we describe below are related to the general problem of distinguishing any two adjacent vertices in a graph. For that problem, we propose two possible interpretations making the 1-2-3 Conjecture popping out; although these two interpretations are close, their purposes and goals are actually a bit different. These differences will eventually permit us to establish connections between the 1-2-3 Conjecture and different other notions.

Let us suppose we have an undirected graph G. In several contexts (for instance when G is supposed to model some network), it might be quite handy to be able to distinguish any two adjacent vertices of G somehow. Of course, many solutions can be employed to achieve that task. In the following two items, we propose two natural solutions, the first one involving a natural graph parameter, the second one involving objects computed from the graph.

• Solution 1: In this solution, we propose to distinguish any two adjacent vertices u and v of G via one of their natural parameters that is very easy to compute, being their degree. Ideally, our graph G is such that for every edge uv we have d(u) d(v), in which case, indeed, whenever considering an edge we are able to distinguish its two ends. When G has this very convenient property, we call it locally irregular. A negative point, however, is that graphs, in general, might be very far from having this ideal property of locally irregular graphs (consider for instance a regular graph); thus, in general, distinguishing adjacent vertices via their degrees is not a viable solution.

In the situation where G is not locally irregular, one possible way to fix the problem is by making G locally irregular somehow. An approach inspired from one considered by Chartrand, Jacobson, Lehel, Oellermann, Ruiz and Saba in [START_REF] Chartrand | Irregular networks[END_REF] for a more general problem, is to try to turn G into a locally irregular multigraph G , by replacing each e of the edges of G by n e ≥ 1 parallel edges joining its ends. Note that "multiplying" edges in this fashion is a way to preserve the structure of G when going to G . In particular, the adjacencies in G are preserved in G .

It is easy to show, using inductive arguments, that if the number of times n e an edge e of G can be multiplied is not bounded, then every graph G having no connected component isomorphic to K 2 can indeed be turned into a locally irregular multigraph G that way. However, regarding our context, it might be that edge multiplications correspond to a very expensive operation, and that we should try to produce G with minimising max e∈E(G) n e . This leads to the following optimisation problem: Given a graph G, what is the smallest k such that G can be turned into a locally irregular multigraph by multiplying each of its edges at most k times?

• Solution 2: In this solution, we propose to distinguish any two adjacent vertices u and v through a proper vertex-colouring of G, which, by definition, indeed assigns different colours to u and v. The problem is that, in general, the minimum number of colours needed to colour G in a proper way, which is its chromatic number χ(G), can be quite large. Indeed, we know that χ(G) can be as large as ∆(G) + 1, which, again, depending on the context might be too demanding.

Instead of using an explicit proper vertex-colouring of G, one way to fix this problem can be to "simulate" a proper vertex-colouring somehow, with hopefully using less resources. One possible way is by weighting the edges of G so that, for every vertex v of G, some "thing" can be computed from the weights on the edges incident to v, and that the resulting "things" actually form a proper vertex-colouring (i.e., no two adjacent vertices are incident to weights yielding the same "thing"). Note that we do not require the simulated proper vertex-colouring to be optimal; indeed, we are here happy as soon as adjacent vertices can be distinguished, and the assigned edge weights are relatively small (so that the induced proper vertex-colouring is obtained through few resources).

One can come up with many candidates as these "things". For instance, the "things" can be the sums, products or multisets of weights incident to the vertices. For a given notion of "thing", an optimisation problem then arises: Given a graph G, what is the smallest k such that, by weighting the edges with weights 1, . . . , k, we can produce "things" forming a proper vertex-colouring?

Let us now focus on Solution 2 above, in the very special case where the "things" are the sums of weights assigned to the incident edges. Then it can be noted that the question at the end of Solution 2 becomes equivalent to that at the end of Solution 1. Indeed, assume that we have a k-edge-weighting ω of G that distinguishes the adjacent vertices via their incident sums. Consider G the multigraph obtained from G by replacing every edge e of G by ω(e) parallel edges. Then G is locally irregular, since the sum incident to a vertex in G becomes the degree of that vertex in G . Since no two adjacent sums are the same in G, this means that not two adjacent degrees are the same in G , which is thus locally irregular. The implication also works the other way around, by the same arguments. All this is illustrated in Figure 2.1.

These concerns are precisely those behind the 1-2-3 Conjecture. Let us now go more formal. Let G be an undirected graph, and ω be an edge-weighting of G. For every vertex u of G, we define σ ω (u) (or simply σ (u) when no ambiguity is possible) the sum of the weights assigned to the edges incident to u, that is

σ (u) = v∈N (u) ω(uv).
Due to one of the analogies above, the parameter σ (u) is sometimes called the weighted degree of u (by ω) in literature. In case σ (u) σ (v) holds for every edge uv of G, we say that ω is neighbour-sum-distinguishing. Note that (b) in Figure 2.1 shows a neighbour-sum-distinguishing 2-edge-weighting of C 4 . We denote by χ e σ (G) the least k such that G admits a neighbour-sumdistinguishing k-edge-weighting, if any. This notation χ e σ should be understood as follows: "χ" means that we are dealing with a chromatic parameter, "σ " means that vertices should be distinguished through their incident sums, and "e" means that these sums are obtained from an edge-weighting. This notation might look a bit awkward to the reader; however, as will be seen later, it permits easy variations that will be used throughout this document.

Before going further, it is a crucial point establishing right away which graphs we are dealing with, when designing neighbour-sum-distinguishing edge-weightings. As mentioned earlier, K 2 is the only problematic (connected) graph. When unbounded weights can be used, this can be proved through straight inductive arguments.

Observation 2.1. For a connected graph G, the parameter χ e σ (G) is not finite if and only if G = K 2 . Thus, χ e σ (G) is defined as long as G does not include K 2 as a connected component. We say that G is nice in such a situation. Now that we have this definition in hand, we can eventually introduce the 1-2-3 Conjecture formally, which is due to Karoński, Łuczak and Thomason.

1-2-3 Conjecture ( [START_REF] Karoński | Edge weights and vertex colours[END_REF]). For every nice graph G, we have χ e σ (G) ≤ 3.

Going back to the problem mentioned in Solution 1 above, the 1-2-3 Conjecture states that, for every nice graph G, we can turn G into a locally irregular multigraph by replacing every edges by 1, 2 or 3 parallel edges. Regarding the problem mentioned in Solution 2, the conjecture states that we can always simulate a (not necessarily optimal) proper vertex-colouring of G via the incident sums inherited from a 3-edge-weighting.

First results and properties

In what follows, we survey some results related to the 1-2-3 Conjecture that are, in my opinion, of interest because either they are among the most important ones of this very topic, or they give some good intuition on the behaviours of the problem.

Easy classes of graphs

First of all, we note that for a nice graph G to have χ e σ (G) = 1, clearly it must have no edge uv with d(u) = d(v). This implies: Observation 2.2. For a nice graph G, we have χ e σ (G) = 1 if and only if G is locally irregular. Also, there are examples of graphs G such that χ e σ (G) > 2; this implies that the value "3" in the 1-2-3 Conjecture cannot be dropped from the equation. This is attested, for instance, by cycles of length congruent to 2 modulo 4. This follows from the fact that, in a neighbour-sumdistinguishing edge-weighting of a graph, if uv is an edge with d(u) = d(v) = 2, then the edge incident to u different from uv must be assigned a weight different from the weight assigned to the edge incident to v different from uv. This is, indeed, to ensure σ (u) σ (v). However, it is not complicated to find neighbour-sum-distinguishing 3-edge-weightings of any cycle with length congruent to 2 modulo 4.

Observation 2.3. For every k ≥ 1, we have χ e σ (C 4k+2 ) = 3. Since graphs G with χ e σ (G) = 1, i.e., the locally irregular ones, are easy to recognise, and there exist graphs G with χ e σ (G) = 3, a natural question that arises is about whether graphs G with χ e σ (G) = 3 form a wide class or not. Unfortunately, there is no good characterisation1 of these graphs (unless P=NP), as first shown by Dudek and Wajc.

Theorem 2.4 ([51]

). Given a graph G, deciding whether χ e σ (G) ≤ 2 holds is NP-complete. Now that it is clear that, in the context of the 1-2-3 Conjecture, we sometimes need to assign weight 3 to edges, let us mention the most important graph classes for which the conjecture was proved. First of all, there is a nice proof that the conjecture is true for complete graphs.

Theorem 2.5 ([48]). For every n ≥ 3, we have χ e σ (K n ) ≤ 3.

Proof. We describe an edge-weighting scheme that we iteratively extend to bigger and bigger complete graphs. That is, starting from a neighbour-sum-distinguishing 3-edge-weighting of K 3 , we repeatedly add a new vertex v joined to all previous vertices, and extend the edgeweighting to the new edges (incident to v) so that no sum conflicts arise. A neighbour-sum-distinguishing 3-edge-weighting of K 3 is obtained by assigning weights 1, 2, 3 to its edges. To get one of K 4 , add a vertex and assign weight 1 to its three incident edges. To get one of K 5 , add a vertex and assign weight 3 to its four incident edges. To get the result for any K n , just generalise these arguments: assuming K n-1 is weighted, add a new vertex and assign weight 1 to its n -1 incident edges if n is even, or weight 3 to these edges otherwise.

It can easily be checked that, at each step, the resulting edge-weighting is neighbour-sumdistinguishing. First, when adding a new vertex and weighting its incident edges, assigning the same weight (1 or 3) guarantees that no sum conflict arises among the previous vertices.

Second, note that, by a 3-edge-weighting of a regular graph, a vertex with all incident edges being weighted 1 (3, respectively) can only be in conflict with vertices having all incident edges being weighted 1 (3, respectively). The weighting scheme above avoids such situations, which means that also the new vertex is not in sum conflict with any other vertex.

The case of 3-chromatic graphs involves another nice trick, which is classical in this field. Theorem 2.6 ([61]). For every connected 3-chromatic graph G, we have χ e σ (G) ≤ 3. We aim at constructing a 3-edge-weighting ω of G by which, for every i ∈ {0, 1, 2}, every vertex v ∈ V i verifies σ (v) ≡ i mod 3. Note that if ω has this property, then for sure it is neighboursum-distinguishing. Also, when considering sums modulo 3, we can use weights 0, 1, 2 instead of 1, 2, 3 (once ω is obtained, 0's can be turned into 3's without breaking the modulo property).

Proof. Let V 0 ∪ V 1 ∪ V 2 be a partition of V (G)
To get such an ω, start from all edges weighted 0, so that all vertices in V 0 have the desired sum modulo 3. We now need to make sure that also the vertices in V 1 and V 2 have desired sums (modulo 3). To that aim, consider the following procedure. We pick any two distinct vertices u, v ∈ V 1 ∪ V 2 that need to be fixed, and consider a walk P joining them. Note that, as traversing P from u to v, alternately modifying (modulo 3) the edge weights by -1, +1, -1, +1, . . . , only the sums of u and v are affected modulo 3. By then choosing P to be either of odd or even length (both types of walks between u and v exist because G is not bipartite), depending on how σ (u) and σ (v) need to be modified, we can make u and v get desired sums. Now, since |V 1 | + |V 2 | is even, it means there are an even number of vertices to fix, which we can do by repeating the walk-switching procedure above for successive pairs of them.

In the proof of Theorem 2.6, we note that it is important that the graph is not bipartite, because this is the key to guaranteeing the existence of both odd-length walks and even-length walks between any two vertices. As pointed out in [START_REF] Karoński | Edge weights and vertex colours[END_REF], the arguments can be generalised to prove that for every connected k-chromatic graph G with k ≥ 3 odd, we have χ e σ (G) ≤ k. When k ≥ 2 is even, there are cases where the same arguments do not work, typically when all sets in the proper k-vertex-colouring of G are of odd size (as, for the whole walk-switching procedure, we need to ensure that the number of sums to fix is even). However, with a bit more efforts, it can be proved that connected k-chromatic graphs G with k ≥ 4 also verify χ e σ (G) ≤ k.

The intriguing case of bipartite graphs

For the case k = 2, that of bipartite graphs, the situation is a bit different, due to the small value of k. Indeed, as pointed out in Observation 2.3, some bipartite graphs G verify χ e σ (G) > 2. To prove that they all verify the 1-2-3 Conjecture, a few more arguments are needed, which we mention below, right before the statement of Theorem 2.9. Before getting to that point, we first go through straight modifications of the proof scheme we use, which allow us to mention nice arguments and side results along the way, which will be needed later in this document.

First, the arguments used in the proof of Theorem 2.6 can be modified by a bit, in order to show the following simple yet important result: Observation 2.7 ( [START_REF] Dudek | On the complexity of vertex-coloring edge-weightings[END_REF]). For every connected bipartite graph G of bipartition A ∪ B with |A| even, there exists a 2-edge-weighting of G where all vertices in A have odd sum, while all vertices in B have even sum. Consequently, χ e σ (G) ≤ 2.

Proof. As in the proof of Theorem 2.6, we may instead use weights 0 and 1 since we consider sums modulo 2. Start from all edges weighted 0, so that the condition is fulfilled for all vertices of B, but for no vertex of A. Then repeatedly consider two vertices u and v in A with bad sums, and a walk P from u to v (which exists since G is connected). Since G is bipartite, this P has even length. Then apply +1, -1, +1, -1, . . . , -1 modulo 2 to the weights of the edges of P as traversing them when going from u and v along P . Again, only the parities of the sums of u and v are altered: they were even and become odd. Thus, this procedure fixes u and v. Now, since |A| is even, then we can just repeat this walk-switching procedure for disjoint pairs of vertices of A, until they all have odd sum. Observation 2.7 is a nice result that has several implications. For instance, it implies that connected bipartite graphs G with χ e σ (G) = 3 have their both partition classes of odd size. It also provides a way for proving that χ e σ (T ) ≤ 2 holds for every nice tree T2 . Theorem 2.8 ( [START_REF] Dudek | On the complexity of vertex-coloring edge-weightings[END_REF]). For every nice tree T , we have χ e σ (T ) ≤ 2.

Proof. If one of the two parts A and B of the bipartition of T has even size, then the result follows from Observation 2.7. So assume A and B have odd size. Let u be a leaf of T , where, say, u ∈ A, and consider T = Tu. Note that T cannot be K 2 , since T is connected and A and B have odd size. In T , the part A \ {u} of the bipartition now has even size; thus, by Observation 2.7, there is a 2-edge-weighting of T where all vertices in A \ {u} have odd sum, while all vertices in B have even sum. We extend this edge-weighting to a neighbour-sumdistinguishing 2-edge-weighting of T by assigning weight 2 to the unique edge incident to u. This way, by that weighting, for every vertex different from u, the parity of its sum is the same as in T ; and therefore for every two adjacent vertices of T , their sums remain different in T . So only u can be in conflict with its unique neighbour. But this is actually not the case as u has sum 2 while its neighbour has sum strictly more than 2 due to another incident edge.

To prove that any nice bipartite graph verifies the 1-2-3 Conjecture, we can proceed similarly as in the proof of Observation 2.7, by considering a bipartition V 0 ∪ V 1 , and, assigning weights 0, 1, 2, aiming, for instance, at sums congruent to 0 or 1 modulo 3 for the vertices in V 0 , and at sums congruent to 2 modulo 3 for the vertices in V 1 .

Theorem 2.9 ( [START_REF] Karoński | Edge weights and vertex colours[END_REF]). For every nice bipartite graph G, we have χ e σ (G) ≤ 3. As seen through the previous results, the case of bipartite graphs is quite interesting in the context of the 1-2-3 Conjecture. For a full understanding of this class of graphs, a missing result at this point is an exhaustive list of all connected bipartite graphs G with χ e σ (G) = 3. As mentioned earlier, such graphs all have their both partition classes of odd size, by Observation 2.7. This condition is not sufficient, however, as, for instance, any nice tree T having its two partition classes of odd size verifies χ e σ (T ) ≤ 2 (recall Theorem 2.8). It is also worthwhile mentioning that the complexity result in Theorem 2.4 does not apply to bipartite graphs (for the hardness reduction from [START_REF] Dudek | On the complexity of vertex-coloring edge-weightings[END_REF] to work, triangles are needed). For some time, a trendy topic of the 1-2-3 Conjecture was about whether there exists a good characterization of bipartite graphs G with χ e σ (G) = 3. Over the years, a few constructions of such graphs were provided, see e.g. [START_REF] Seamone | The 1-2-3 Conjecture and related problems: a survey[END_REF] for a list.

An answer to this problem was given in 2016 by Thomassen, Wu and Zhang [START_REF] Thomassen | The 3-flow conjecture, factors modulo k, and the 1-2-3-conjecture[END_REF], who proved that connected bipartite graphs G with χ e σ (G) = 3 are precisely odd multi-cacti, which can be recognised easily. These graphs are defined as follows (the comprehensive definition is from [START_REF] Szabo Lyngsie | On neighbour sum-distinguishing {0, 1}-weightings of bipartite graphs[END_REF]; refer to Figure 2.2 for an illustration):

"Take a collection of cycles of length 2 modulo 4, each of which has edges coloured alternately red and green. Then form a connected simple graph by pasting the cycles together, one by one, in a tree-like fashion along green edges; the resulting graph is an odd multi-cactus. The graph with one green edge and two vertices (K 2 ) is also an odd multi-cactus. When replacing a green edge of an odd multi-cactus by a green edge of any multiplicity, we again obtain an odd multi-cactus."

The intuition why the structure of odd multi-cacti is indeed annoying when using only weights 1, 2 (and, actually, any two weights a, b), is the following. By construction, an odd

u v (a) u v (b) u v (c) u v (d) u v (e)
Figure 2.2: Constructing an odd multi-cactus through several steps, from K 2 (a). Red-green paths with length at least 5 congruent to 1 modulo 4 are being attached onto the green edge uv through steps (b) to (d). In step (e), (green) paths of length 1 are added, which corresponds to increasing the multiplicity of some green edges. multi-cactus G is obtained from K 2 by repeatedly taking two adjacent vertices uv and joining them by a new path P of length 4k + 1. As described before the proof of Observation 2.3, when weighting the edges of P with 1, 2, it can be checked that, due to the length of P , the edge of P incident to u and the edge of P incident to v necessarily get assigned the same weight. Thus, from the point of view of u and v, weighting P is similar to weighting another edge joining them. This means that finding a neighbour-sum-distinguishing 2-edge-weighting of G is sort of equivalent to finding one of G , the odd multi-cactus obtained from G by contracting P to another edge uv. By repeating this process of contracting paths that are equivalent to edges, by how odd multi-cacti are constructed, it can be deduced that finding a neighbour-sumdistinguishing 2-edge-weighting of G is equivalent to finding one of K 2 , which is impossible.

Proving that χ e σ (G) ≤ 2 holds whenever G is a connected bipartite graph that is not an odd multi-cactus is much more complicated. The proof of this result of Thomassen, Wu and Zhang builds upon several successive deductions that led to the precise structure of odd multi-cacti. Most of these deductions make use of Observation 2.7, which is one of the key arguments in this context. For instance, in [START_REF] Lu | Vertex-coloring 2-edge-weighting of graphs[END_REF], it was proved that χ e σ (G) ≤ 2 holds whenever G is a 3-connected bipartite graph. In [START_REF] Thomassen | The 3-flow conjecture, factors modulo k, and the 1-2-3-conjecture[END_REF], some of the steps (towards proving the result on odd multi-cacti) were to prove that the same conclusion holds when G is a bipartite graph with minimum degree at least 3, or when G is connected and has cut-vertices. By establishing results of this kind little by little, this converged to one of the nicest results around the 1-2-3 Conjecture. Theorem 2.10 ( [START_REF] Thomassen | The 3-flow conjecture, factors modulo k, and the 1-2-3-conjecture[END_REF]). Connected bipartite graphs G with χ e σ (G) = 3 are precisely odd multi-cacti. Consequently, the decision problem in Theorem 2.4 is polynomial-time solvable when restricted to bipartite graphs.

Bounds towards the conjecture

A natural step to consider towards the 1-2-3 Conjecture is to prove weaker versions where larger weights can be used, i.e., to prove that for some k > 3, we have χ e σ (G) ≤ k for every nice graph G. Several better and better results of this sort have been obtained over the years, and what is truly interesting is the types of new arguments which were designed and employed. Another quite interesting aspect is the fact that, as the bounds decreased through time, the proofs have not gained in complexity as one could expect, but instead converged to very fluid and elegant proofs. This might be an indication that, over the years, perhaps the mechanisms behind the 1-2-3 Conjecture have been understood better and better.

Although it does not quite match the desired type of bound, it is worthwhile mentioning that, in their seminal paper [START_REF] Karoński | Edge weights and vertex colours[END_REF], Karoński, Łuczak and Thomason proved that there is a set of 183 real numbers that permit to weight the edges of every nice graph in a neighboursum-distinguishing way. The proof of that result made use of probabilistic arguments, which explains the large number of weights. An interesting point is that this result is, to the best of my knowledge, the only one that established a weighting result of this type using probabilistic arguments. All incoming improvements were established via constructive arguments only.

Successive bounds of the sort above were later established over the years. The first result of this kind is that χ e σ (G) ≤ 30 holds for every nice graph G, which was proved by Addario-Berry, Dalal, McDiarmid, Reed and Thomason [START_REF] Addario-Berry | Vertexcolouring edge-weightings[END_REF]. The proof of that result made use of intricate arguments that would later be improved and used in most of the next improvements of the bound. Notably, the proof involves:

• Considering independent sets of vertices, which can freely get the same sum by neighboursum-distinguishing edge-weightings (in the spirit of the proof of Theorem 2.6), and, more precisely, independent sets joined by many edges (for more weighting possibilities).

• Finding subgraphs in which the vertex degrees have particular properties. This is because weighting such subgraphs can provide a "skeleton" of sums that can perhaps be preserved when weighting the remaining edges not in the subgraphs. For instance, if we were to finding a neighbour-sum-distinguishing {0, 1}-edge-weighting of a graph G, then one could e.g. consider a spanning locally irregular subgraph G of G, assign weight 1 to all edges of G , and weight 0 to all remaining edges of G. Thus the sums in G would remain the same as in G , and maybe such an edge-weighting can be a good starting point.

Improvements of such ingredients led Addario-Berry, Dalal and Reed to show, in [START_REF] Addario-Berry | Degree constrained subgraphs[END_REF], that every nice graph G verifies χ e σ (G) ≤ 16, before Wang and Yu, by a more careful analysis, later showed, in [START_REF] Wang | On vertex-coloring 13-edge-weighting[END_REF], that we even always have χ e σ (G) ≤ 13. Some breakthrough was made a few years later, through the design of much nicer arguments. Although the proofs above were really nice, they were also complex due to the intricate use of a number of results that were as optimised as possible -so optimised that further improvements would have needed lots of efforts. Still, the proofs above introduced some ideas that are still present in the proof of the best result we know so far towards the 1-2-3 Conjecture.

Before stating the last bound improvement towards the 1-2-3 Conjecture, let us first give an insight in the general ideas behind its proof. In the 1-2-3 Conjecture, we aim at proving that almost all graphs have a particular property. A first natural idea that would come to the mind of any person into discrete mathematics, would be to try out inductive arguments. The thing is that, unfortunately, neighbour-sum-distinguishing edge-weightings hardly comply with inductive arguments, because of several reasons. A first minor reason, but which we should always keep at the back of our mind, is that when removing some structure from a nice graph G, we might end up with a graph that is not nice any more. A much more major reason, is that when extending a partial neighbour-sum-distinguishing edge-weighting to an edge uv, not only we perhaps need to be careful that u and v do not get the same sum (which is actually independent of the weight assigned to uv), but also we have to make sure that the sum of u does not get equal to that of some of its other neighbours, and similarly for v. The problem is that both u and v might have lots of other such neighbours, as many as ∆(G) -1, while, in this context, there are only a constant number of possible weights we can assign to uv.

For these reasons, using inductive arguments without clever additional assumptions is a terrible idea that, unless we are in very specific contexts, has little chances to work. This is precisely what Kalkowski, Karoński and Pfender managed to overcome to prove the best result towards the 1-2-3 Conjecture [START_REF] Kalkowski | Vertex-coloring edge-weightings: towards the 1-2-3 Conjecture[END_REF]. Building upon a brilliant weighting algorithm (to be described in full details in Section 2.2.1) originally designed by Kalkowski to deal with a total version of the 1-2-3 Conjecture (see below), they managed to describe an inductive weighting procedure, leading to a simple algorithm that finds a neighbour-sum-distinguishing 5-edgeweighting of any nice graph.

Theorem 2.11 ([60]). For every nice graph G, we have χ e σ (G) ≤ 5. In very brief words, the idea behind the algorithm is to make an inductive proof work out. To that aim, the vertices v 1 , . . . , v n are processed one by one. Whenever considering a vertex v i , we have to weight the edges going to its backward neighbours, i.e., neighbours v j with j < i. To make sure that, when weighting an edge v j v i , no sum conflict involving v j and another of its neighbours arises, the clever idea is to have two possible valid sums for each vertex chosen so that, as long as a vertex has sum one of its two valid sums, no sum conflict can arise. Having such two sums defined for every backward neighbour v j of v i is then convenient because it guarantees that there are ways to weight the backward edges of v i without creating conflicts.

These words are of course far from depicting all technicalities and subtleties behind the proof of Theorem 2.11. But its main general idea is to make inductive arguments work, by taking care of all issues that may occur when applying a naive inductive strategy. Again, the full details on the precise procedure will be provided in Section 2.2.1.

Side aspects

We now survey some aspects of the 1-2-3 Conjecture that we think are of interest. These aspects cover, in particular, more or less natural variants of the original conjecture.

Multiset version

Addario-Berry, Aldred, Dalal and Reed proposed in [START_REF] Addario-Berry | Vertex colouring edge partitions[END_REF] a weakening of the 1-2-3 Conjecture, its multiset version, based on the observation that if σ (u) σ (v) holds for any two vertices u, v in an edge-weighted graph, then the multisets of weights incident to u and v cannot be identical. Let G be a graph, and ω be an edge-weighting of G. To every vertex u of G, one can assign to u the colour µ(u) being the multiset of weights assigned to the edges incident to u. Recall that a multiset is essentially a set in which a single element is allowed to appear more than once. We say that ω is neighbour-multiset-distinguishing if µ(u) µ(v) for every edge uv of G, i.e., the resulting function µ is a proper vertex-colouring of G. Assuming G is nice, we denote by χ e µ (G) the least k such that G admits neighbour-multiset-distinguishing k-edge-weightings.

As mentioned above, every neighbour-sum-distinguishing edge-weighting is also neighbourmultiset-distinguishing, which means that χ e µ (G) ≤ χ e σ (G) holds for every nice graph G. Obviously the contrary is not always true, however. Still, these simple observations show that neighbour-multiset-distinguishing edge-weightings should in general be easier to design. In particular, we note that, for any two vertices u and v, we have µ(u) µ(v) whenever d(u) d (v). So here we need to pay attention only to distinguishing adjacent vertices with the same degree.

It can be noted that for some graphs G with χ e σ (G) = 3, such as some cycles and complete graphs, we also have χ e µ (G) = 3. So it makes sense wondering about a straight analogue of the 1-2-3 Conjecture for neighbour-multiset-distinguishing edge-weightings.

Conjecture 2.12 ([1]

). For every nice graph G, we have χ e µ (G) ≤ 3. Conjecture 2.12 directly benefits from all results on the 1-2-3 Conjecture mentioned earlier in this chapter. In particular, the 1-2-3 Conjecture, if proved true, would directly imply Conjecture 2.12, and, from Theorem 2.11, we already know that χ e µ (G) ≤ 5 holds for every nice graph G. There are additional progresses, however, holding for Conjecture 2.12 but not for the 1-2-3 Conjecture that are worth mentioning. In particular, in the seminal work [START_REF] Addario-Berry | Vertex colouring edge partitions[END_REF], the authors proved that every graph G with δ(G) ≥ 1000 verifies Conjecture 2.12. An even more interesting result they gave is that χ e µ (G) ≤ 4 holds for every nice graph G, which is one step closer to their conjecture. This very nice result is, in particular, a consequence of the following lemma, which suits so cleverly the context that we must mention it:

Lemma 2.13 ([1]). Let G be a connected graph with χ(G) > 3. Then, there is a partition V 0 ∪ V 1 ∪ V 2 of V (G)
such that, for every vertex v in any part V i :

• v has at least as many neighbours in V i+1 mod 3 than it has in V i ;

• v has at least one neighbour in V i+1 mod 3 .

The proof of Lemma 2.13 is actually genuinely simple, as it is mostly by considering a tripartition

V 0 ∪ V 1 ∪ V 2 of V (G)
maximising the number of edges between the V i 's. Proving that χ e µ (G) ≤ 4 holds for every nice graph G can then be done easily in the following way. If χ(G) ≤ 3, then the result follows e.g. from Theorem 2.6 or 2.9. Now, if χ(G) > 3, then we can partition G following Lemma 2.13, and, taking advantage of the many edges between the V i 's, there are easy neighbour-multiset-distinguishing 4-edge-weightings of G that can be designed. Consider for instance the following edge-weighting assigning weights in {0, 1, 2, * }. For every i ∈ {0, 1, 2}, assign weight i to all edges in V i . Now, for every v ∈ V i , select a certain number m v of edges going to V i+1 mod 3 and assign weight i to these edges, in such a way that no two adjacent vertices of V i are incident to the same total number of edges assigned weight i. This is possible, because, in V i , every vertex has at least as many neighbours in V i+1 mod 3 than it has in V i . Finally assign weight * to all edges that have not been weighted yet. Note now that we have µ(u) µ(v) whenever u, v ∈ V i are adjacent, since u and v are not incident to the same number of edges assigned weight i. The same holds when u ∈ V i and v ∈ V i+1 mod 3 , since v is incident to edges assigned weight i + 1 mod 3, while u is not incident to such edges.

Total version

By the time where Theorem 2.11 was not a thing yet, some researchers considered weaker versions of the 1-2-3 Conjecture to investigate. The multiset version of the 1-2-3 Conjecture introduced earlier is one of those such versions. Another interesting version, the total version, can be motivated by the very simple observation that if we pick a graph G and attach a pending degree-1 vertex v to every vertex v of G, resulting in a graph G (being nothing but the corona product of G and K 1 ), then G should be easier to weight than G. This is because when considering edge-weightings assigning strictly positive weights only, a degree-1 vertex cannot be involved in a sum conflict with its unique neighbour. In other words, when designing a neighbour-sum-distinguishing edge-weighting of G , we do not have to be careful with the attached degree-1 vertices causing conflicts. An implication of that is that weighting an edge v v in G can be perceived as a very local way to alter σ (v) without altering the sum of its neighbours in G. So, in a sense, edge-weighting G is similar to edge-weighting G with the exception that for every vertex we locally have the freedom to modify its sum by a bit.

There is another interpretation of this through employing total-weightings. Recall that, for a graph G, a total-weighting ω of G is an assignment of weights to both its edges and vertices. Regarding the context above, the sum σ t (u) of a vertex u (by ω) is now the sum of its "incident weights", including its own weight; that is

σ t (u) = ω(u) + v∈N (u) ω(uv).
Again, we say that ω is neighbour-sum-distinguishing if σ t is a proper vertex-colouring of G, and χ t σ (G) denotes the least k where G admits neighbour-sum-distinguishing k-total-weightings.

Note that for every nice graph G, we have χ t σ (G) ≤ χ e σ (G), because every neighbour-sumdistinguishing k-edge-weighting can be turned into a neighbour-sum-distinguishing k-totalweighting by assigning weight 1 to all vertices. Furthermore, it can be noted that, this time, we have χ t σ (K 2 ) = 2. From these arguments, we get that χ t σ (G) is defined for every graph G.

These notions were first considered by Przybyło and Woźniak in [START_REF] Przybyło | On a 1,2 Conjecture[END_REF]. Noticing that χ t σ (G) ≤ χ e σ (G) holds for every nice graph G (and thus all results mentioned so far on the 1-2-3 Conjecture also apply here), and that all known graphs G with χ e σ (G) = 3 admit neighbour-sumdistinguishing 2-total-weightings, they wondered whether being allowed to locally alter the vertices' sums is strong enough to decrease further the number of needed weights. This resulted in the following conjecture:

1-2 Conjecture ( [START_REF] Przybyło | On a 1,2 Conjecture[END_REF]). For every graph G, we have χ t σ (G) ≤ 2. Although quite daring, no counterexample to the 1-2 Conjecture is known to date. As mentioned earlier, it was actually verified that all known "bad guys" for the 1-2-3 Conjecture, i.e., those known graphs G with χ e σ (G) = 3, comply with the 1-2 Conjecture. Przybyło and Woźniak also provided additional support by proving the 1-2 Conjecture for graphs for which the 1-2-3 Conjecture is not even known to hold, such as 4-regular graphs.

As mentioned earlier, the main point for mentioning the 1-2 Conjecture is that the main result towards it led to Theorem 2.11, which is by far the most important result towards the 1-2-3 Conjecture to date. This main result, due to Kalkowski, is essentially that the 1-2-3 Conjecture holds when restricted to total-weightings. Actually, even something stronger is true, and to state it we need a slightly refined definition. For a graph G and two integers x, y ≥ 1, an (x, y)-total-weighting is a total-weighting of G where vertices are assigned weights in {1, . . . , x} and edges are assigned weights in {1, . . . , y}.

Theorem 2.14 ([59]

). Every graph G admits a neighbour-sum-distinguishing (2, 3)-total-weighting. Consequently, for every graph G we have χ t σ (G) ≤ 3. A very remarkable fact behind the result of Kalkowski is not only that his result is very close to the 1-2-3 Conjecture, but also that his proof is very brilliant and elegant, while most previous results establishing bounds were a lot more involved and tedious. This proof is by means of a very simple algorithm, which will be described in details in upcoming Section 2.2.1, as understanding it will be necessary for getting some of the results presented in this chapter.

Using different weights

By arguments described earlier, there are certainly reasons, in the context of the 1-2-3 Conjecture, for focusing on edge-weightings assigning consecutive weights 1, . . . , k. But, from, at least, the theoretical point of view, a legitimate question is whether assigning other weights changes the problem a lot. There are situations where, indeed, considering different weights does not change anything. For instance, the arguments in the proof of Observation 2.7 still apply when assigning two weights a, b with distinct parity. Actually, when assigning two weights a, b only, there are situations where the actual value of a and b does not matter; such as: Observation 2.15. Let G be a regular graph, and a, b be any two distinct integers. Any neighboursum-distinguishing {a, b}-edge-weighting of G yields a decomposition into two locally irregular graphs, and vice versa. Consequently, a neighbour-sum-distinguishing {a, b}-edge-weighting of G also yields a neighbour-sum-distinguishing {a , b }-edge-weighting for any pair {a , b }. Observation 2.15, rephrased differently, states that, when edge-weighting regular graphs with only two weights a, b, the actual value of a and b does not matter. A nice consequence follows from a result Ahadi, Dehghan and Sadeghi, who proved in [START_REF] Ahadi | Algorithmic complexity of proper labeling problems[END_REF] that Theorem 2.4 also holds when restricted to cubic graphs. This yields: Theorem 2. 16 ([4]). Given a graph G and any two distinct integers a, b, deciding whether G admits a neighbour-sum-distinguishing {a, b}-edge-weighting is NP-complete.

Let us focus a bit more on the case where only two weights a, b are assigned. In [START_REF] Thomassen | The 3-flow conjecture, factors modulo k, and the 1-2-3-conjecture[END_REF], Thomassen, Wu and Zhang say that a graph has the {a, b}-property if it admits neighbour-sumdistinguishing {a, b}-edge-weightings. Theorem 2.16 means that, for any two a, b, there is, in general, no good characterisation of graphs with the {a, b}-property (unless P=NP). The situation might be a bit different for bipartite graphs however, since there is a good characterisation of bipartite graphs with the {1, 2}-property, recall Theorem 2.10. An interesting question is then whether for any two a, b, there is a good characterisation for bipartite graphs with the {a, b}-property. Some partial results on this sort can be found in the literature. In particular, the results in [START_REF] Thomassen | The 3-flow conjecture, factors modulo k, and the 1-2-3-conjecture[END_REF] actually imply that, for a and b with distinct parity, bipartite graphs without the {a, b}-property have their two partition classes of odd cardinality, and they thus have even order. Reusing some ideas from [START_REF] Thomassen | The 3-flow conjecture, factors modulo k, and the 1-2-3-conjecture[END_REF], Lyngsie later considered the {0, 1}-property for bipartite graphs in [START_REF] Szabo Lyngsie | On neighbour sum-distinguishing {0, 1}-weightings of bipartite graphs[END_REF]. His main result is a good characterisation of 2-edge-connected bipartite graphs without the {0, 1}-property, which turn out to be nothing but the class of odd multi-cacti. This result was established, in particular, through aforementioned tools and results for cases where a and b have different parity. However, both Thomassen et al. and Lyngsie observed that there exist infinitely many separable (i.e., with cut-vertices) bipartite graphs (even trees) without the {0, 1}-property. Thus, the story of bipartite graphs and the {0, 1}-property is not over yet.

Keep in mind also that multiplying all weights of a neighbour-sum-distinguishing edgeweighting by a same non-zero integer results in another neighbour-sum-distinguishing edgeweighting; from the results above, this yields more partial results towards characterising bipartite graphs without some {a, b}-property. For instance, Theorem 2.10 implies that, for every k ≥ 1, connected bipartite graphs without the {k, 2k}-property are exactly odd multi-cacti.

Let us now go back closer to the 1-2-3 Conjecture, to assigning more than two weights. To date, there is no known triple {a, b, c} of constant positive weights such that all nice graphs admit neighbour-sum-distinguishing {a, b, c}-edge-weightings. It is however believed that we should be able to weight all nice graphs this way, whatever {a, b, c} be. Something stronger is actually believed to be true. Let us introduce some more definitions and notation. Consider a graph G, and let L be an assignment of integers to the edges of G (i.e., to each edge e is assigned a set L(e) of integers). An L-list-weighting of G is an edge-weighting ω where ω(e) ∈ L(e) for every edge e. We denote by ch e σ (G) the least k such that G admits a neighbour-sum-distinguishing L-list-weighting for every list assignment L assigning at most k weights to every edge (if any such weighting exists). Now we can state the following more general list version of the 1-2-3 Conjecture, proposed by Bartnicki, Grytczuk and Niwcyk in [START_REF] Bartnicki | Weight choosability of graphs[END_REF]: Conjecture 2.17 ([10]). For every nice graph G, we have ch e σ (G) ≤ 3. Conjecture 2.17 is of course much more intriguing than the original 1-2-3 Conjecture. Yet, no counterexample to it was exhibited through the years, since its introduction. Bartnicki, Grytczuk and Niwcyk, in their seminal work, actually developed a method based on algebraic tools, and more precisely on the so-called Combinatorial Nullstellensatz of Alon [START_REF] Alon | Combinatorial Nullstellensatz[END_REF], for dealing with their conjecture. Through their method, they notably proved that Conjecture 2.17 holds for trees, complete graphs, and complete bipartite graphs. Refinements of their method led other researchers to provide general upper bounds on ch e σ (G) for any nice graph G (see [START_REF] Ding | Graphs are (1, ∆+1)choosable[END_REF] for most of the best known results to date). However, all known general upper bounds at the moment are not constant, as they are expressed as a function of the maximum degree ∆(G). Towards Conjecture 2.17, an important direction nowadays is actually proving that, for some absolute constant c, we have ch e σ (G) ≤ c for every nice graph G. Let us conclude by mentioning that there is also a list version of the 1-2 Conjecture, raised in [START_REF] Wong | Total weight choosability of graphs[END_REF] by Wong and Zhu, where vertices and edges must be weighted with weights from assigned lists of size 2. A remarkable result here, given in [START_REF] Wong | Every graph is (2, 3)-choosable[END_REF] by the same authors, is that, here, a constant bound, namely 3, was proved. In other words, the authors proved a list version of Theorem 2.14. The proof is again by means of the Combinatorial Nullstellensatz, which makes this tool a very powerful and promising one in this context.

Results on main aspects

In this section, we present two series of results on aspects of prime importance behind the 1-2-3 Conjecture. We start off in Section 2.2.1 with a result from [START_REF] Bensmail | A 1-2-3-4 result for the 1-2-3 Conjecture in 5-regular graphs[END_REF] being an improvement of Theorem 2.11 for a particular graph class, that opened the way for more progress on the topic. We then continue in Section 2.2.2 with results obtained with Mc Inerney and Lyngsie in [START_REF] Bensmail | On {a, b}-edge-weightings of bipartite graphs with odd a, b[END_REF] on neighbour-sum-distinguishing {a, b}-edge-weightings of bipartite graphs with a, b odd.

2.2.1

Weighting 5-regular graphs with 1, 2, 3, 4

In this section, we focus on the 1-2-3 Conjecture for regular graphs. One main motivation for this is that nice regular graphs can, intuitively, be considered as being among the most complicated graphs for the 1-2-3 Conjecture. This is because all vertices in a regular graph have the same set of possible sums by an edge-weighting. Due to Theorem 2.11, we know that, for every nice regular graph G, we have χ e σ (G) ≤ 5. Our main result in this section is that for 5-regular graphs (which are obviously all nice) this bound can be decreased one step lower: Theorem 2.18. For every 5-regular graph G, we have χ e σ (G) ≤ 4. Another point for considering 5-regular graphs is that they form, in a sense, the class of regular graphs with smallest degree for which the upper bound of 4 on χ e σ remains to be established. Indeed, for cubic graphs the 1-2-3 Conjecture holds by Theorem 2.6 (and the fact that K 4 also verifies the conjecture), while, for 4-regular graphs, a 1-2-3-4 result also exists according to [START_REF] Seamone | The 1-2-3 Conjecture and related problems: a survey[END_REF] (because K 5 verifies the 1-2-3 Conjecture, and we have χ e σ (G) ≤ 4 for every graph G with χ(G) ≤ 4). These are all known results of literature being better than the general Theorem 2.11. Another more important point for consideration lies in the method we use. Indeed, to prove Theorem 2.18, we introduce another modification of Kalkowski's Algorithm that is rather different from those designed so far. We believe this is of interest, as Kalkowski's Algorithm remains, to date, one of the main methods used to deal with the 1-2-3 Conjecture. Lastly, although one may regard 5-regular graphs as a quite restricted class of graphs, our method actually also applies to less natural classes of graphs. Our method has actually the potential to be generalised to more graph classes.

The rest of this section is dedicated to describing the proof of Theorem 2.18.

Kalkowski's Algorithm

The main ingredient in our proof of Theorem 2.18 is Kalkowski's Algorithm, that led to proving Theorem 2.14 and later to proving Theorem 2.11. As already mentioned, this algorithm is a quite clever and brilliant one due to its simplicity, especially when compared with the proof schemes employed to prove previous results towards the 1-2-3 Conjecture. Because of all these reasons, and because the proofs in both [START_REF] Kalkowski | A note on the 1,2-Conjecture[END_REF] and [START_REF] Kalkowski | Vertex-coloring edge-weightings: towards the 1-2-3 Conjecture[END_REF] are a bit indigest, we would like to take the occasion of this document to provide a more reader-friendly proof of Kalkowski's result. The proof of Theorem 2.14 (which, recall, is about the 1-2 Conjecture) by Kalkowski in [START_REF] Kalkowski | A note on the 1,2-Conjecture[END_REF] relies on the fact that every graph admits a 3-edge-weighting which is almost neighbour-sumdistinguishing, in the following sense.

Lemma 2.19 ([59]). For every graph G, there is a proper vertex-colouring

φ : V (G) → N * such that G admits a 3-edge-weighting ω verifying σ (v) ∈ Φ(v) := (φ(v) -1, φ(v)) for every vertex v of G.
The proof of Theorem 2.14 essentially consists in 1) deducing a 3-edge-weighting ω of G as guaranteed by Lemma 2.19, then 2) assigning weight 1 to every vertex v verifying σ ω (v) = φ(v), and 3) assigning weight 2 to every vertex v verifying σ ω (v) = φ(v) -1. This results in

v j ¡ 2 → 1 2 ¡ 2 → 1 2 Φ 7 | 8 Φ 6 | 7 Φ 8 | 9 Φ 5 | 6 Φ undef. | undef. ↑ ¡ ¡ ↑ ↑ ↑ ¡ ¡ ↑ ↑ Figure 2.3:
Performing valid adjustments in the proof of Lemma 2.19. Vertex v j has initial incident sum 8, while its backward neighbours will eventually have final incident sums 7, 8, 9.

We perform valid adjustments backwards so that σ (v j ) = 6, which is an available final incident sum for v j . Then we set Φ(v j ) = [START_REF] Alon | Combinatorial Nullstellensatz[END_REF][START_REF] Alon | The Probabilistic Method[END_REF].

a neighbour-sum-distinguishing 3-total-weighting of G as, for every vertex v, the obtained incident sum is φ(v) + 1 with φ being a proper vertex-colouring of G. Lemma 2.19 is thus the cornerstone that makes Theorem 2.14 possible. For that reason, we provide a detailed proof. A remarkable point is that the proof is fully algorithmic and simple.

Proof of Lemma 2.19. We can assume that G is connected as otherwise we may argue componentwise. Let v 1 , . . . , v n be the vertices of G ordered in an arbitrary way. The original proof of Kalkowski, which is purely algorithmic, consists in starting from an original 3-edge-weighting ω of G, then processing the v i 's one after another, following the order over their indexes, without coming back at any point, and, whenever treating a new vertex v i , modifying the weights incident to v i so that Φ(v i ) can be chosen conveniently, and σ (v i ) belongs to Φ(v i ). In other words, the Φ(v i )'s are determined on the fly, while ω is being modified at each step to guarantee their existence. Hence, once the algorithm is over, both Φ and ω are obtained.

More precisely, the algorithm goes as follows. We start from ω assigning weight 2 to every edge of G, and from φ(v i ) (and thus Φ(v i )) being undefined for every v i . The algorithm will respect, during its course, i.e., at every step, the following properties:

1. For every already-treated vertex v i , the pair

Φ(v i ) = (φ(v i ) -1, φ(v i )) is defined, i.e., φ(v i )
was chosen, and we have σ

(v i ) ∈ Φ(v i ).
2. For every two already-treated adjacent vertices v i and v j , we have φ(v i ) φ(v j ).

3. For every edge v i v j with i < j, the weight ω(v i v j ) can only be modified when treating v j .

We note that Property 2 allows Φ(v i ) ∩ Φ(v j ) to be non-empty, provided φ(v i ) and φ(v j ) are different. Furthermore, Property 3 implies 1) that every edge weight is modified at most once during the algorithm's course, and 2) that, whenever treating a new vertex v j , all backward edges incident to v j , i.e., those edges of the form v i v j with i < j, are assigned weight 2 by ω.

We now describe the general behaviour of the algorithm (see Figure 2.3 for an illustration). Assume all vertices v 1 , . . . , v j-1 have already been treated during the algorithm's course, with Properties 1 to 3 being maintained, and that the next vertex, v j , is considered (we have j = 0 at the very first step). Let b ≤ d(v j ) denote the number of backward neighbours of v j (i.e., vertices v i , with i < j, neighbouring v j ), and arbitrarily denote these vertices by u 1 , . . . , u b . As said above, remind that we have ω(u

1 v j ) = • • • = ω(u b v j ) = 2 at
this point of the algorithm. In order to define φ(v j ), and so Φ(v j ), with maintaining Property 1, and so that v j itself satisfies Properties 1 and 2 (once it is treated), we will alter some of the weights of the backward edges incident to v j . Note that we have to be careful, as, when doing so, one of the u i 's may not fulfil the second part of Property 1 any more. However, since, for every u i , we have σ (u i ) ∈ Φ(u i ) and ω(u i v j ) = 2, we note that the weight 2 on u i v j can be either incremented or decremented with preserving the fact that σ (u i ) ∈ Φ(u i ). Actually, exactly one of these two operations preserves this for each u i v j . We call a valid adjustment the operation of changing the value of ω(u i v j ) by applying the correct modification. Hence, by performing valid adjustments to the backward edges incident to v j , we can modify σ (v j ) without having any of the u i 's violating Property 1.

We hence just have to show that there is a set of valid adjustments to the backward edges incident to v j which makes σ (v j ) belonging to Φ(v j ), so that Property 1 is fully met, for some Φ(v j ) = (φ(v j ) -1, φ(v j )) verifying Property 2. As our proof of Theorem 2.18 partly depends on the existence of such valid adjustments, we prove their existence in the following claim.

Claim 2.20. Assume all of u 1 , . . . , u b have been treated by the algorithm, i.e., the u i 's verify Property 1, and that v j is being considered. Then there is a set of valid adjustments to the backward edges incident to v j for which we get σ

(v j ) ∈ Φ(v j ) for some Φ(v j ) = (φ(v j ) -1, φ(v j )) verifying Property 2.
Proof of the claim. When performing a valid adjustment to a backward edge incident to v j , the value of σ (v j ) changes. We only need to show that, by performing valid adjustments, we can make σ (v j ) or σ (v j ) + 1 reach a value not in {φ(u 1 ), . . . , φ(u b )}. Such a value will be our φ(v j ).

Assume s of the valid adjustments to the backward edges incident to v j are decrements, while t of the valid adjustments are increments. So we have b = s + t. By performing one, two, . . . , s decrements, we make σ (v j ) decrease by 1, 2, . . . , s. Conversely, by performing one, two, . . . , t increments, we make σ (v j ) increase by 1,2, . . . , t. Hence, by performing some valid adjustments to the backward edges incident to v j , we can modify σ (v j ) to any value among S = {σ (v j )s, . . . , σ (v j ), . . . , σ (v j ) + t}, which includes s + t + 1 = b + 1 elements. Hence, the set S \ {φ(u 1 ), . . . , φ(u b )} is non-empty, and we can just choose φ(v j ) as being any element of this difference, and set Φ(v j ) = (φ(v j ) -1, φ(v j )). The claimed valid adjustments hence exist.

Hence, when considering v j , we can, according to Claim 2.20, perform valid adjustments to the backward edges incident to v j yielding a Φ(v j ) verifying Properties 1 and 2, while the u i 's still verify Property 1. Besides, since valid adjustments concern backward edges of v j only, Property 3 is still respected. The algorithm can hence pursue its course, hence fully build the claimed edge-weighting, concluding the proof.

Going to the edge-weighting context

Let us now discuss how Kalkowski's Algorithm (being essentially the proof of Lemma 2. [START_REF] Baudon | Partitioning Harary graphs into connected subgraphs containing prescribed vertices[END_REF]) can be adapted in the edge-weighting context. The strategy proposed, in [START_REF] Kalkowski | Vertex-coloring edge-weightings: towards the 1-2-3 Conjecture[END_REF], by Kalkowski, Karoński and Pfender in order to prove Theorem 2.11, relies on several modifications of the algorithm which we describe roughly. First, all Φ(v i )'s are now of the form (φ(v i ) -2, φ(v i )). Then, since, in the edge version, it is not possible to locally adjust a vertex's weight to modify its incident sum, it is required, at any point of their modified algorithm, that Φ(v i ) ∩ Φ(v j ) is empty for every two adjacent vertices v i and v j . Since the latter condition is much stronger than in Kalkowski's original algorithm, an analogue of Claim 2.20 does not immediately hold. To offset this point, their algorithm is now allowed to adjust the weight of a forward edge (so the ordering v 1 , . . . , v n must guarantee that every v i (but v n ) has a forward neighbour). The price for Kalkowski, Karoński and Pfender's algorithm to work, i.e., to have properties analogous to Properties 1 to 3 to be maintained during its course, is the use of more edge weights.

Our proof of Theorem 2.18 is, essentially, another modification of Kalkowski's Algorithm that is, in some sense, closer to the original algorithm than is the approach imagined by Kalkowski, Karoński and Pfender. The very basic idea behind our proof is to apply Kalkowski's Algorithm in the edge context by simulating vertex weights by edge weights. Assume G is a graph we want to edge-weight in a neighbour-sum-distinguishing way, and let W ∪ H be a partition of V (G) such that every vertex of H has at least one neighbour in W . According to that property, every vertex u ∈ H has some incident edges going to W . We call those edges the private edges of u. We note, now, that a neighbour-sum-distinguishing total-weighting ω of G[H] naturally yields a partial edge-weighting ω of G which distinguishes the adjacent vertices of H only. One can indeed just start from ω being ω, and then simulate every vertex weight ω(u) by setting ω (uv) = ω(u), where uv is a private edge of u.

Of course, this idea, as roughly stated above, suffers many issues which need to be pointed out. One issue is that not all edges of G get weighted by ω ; this is, in particular, the case for the private edges not chosen in the last stage. Another issue is that G[H] may consist in several connected components, some of which, in particular the ones with no edges, must be treated differently. Another one main issue is that, by a neighbour-sum-distinguishing edge-weighting of G, not only the adjacent vertices in G[H] must receive different sums. In particular, we also have to guarantee that σ (u) σ (v) holds for 1) adjacent vertices u, v ∈ W , and 2) adjacent vertices u ∈ H and v ∈ W . The first of these cases is easy to handle, as we may just require W to be an independent set. To guarantee this, we can just make use of the folklore fact that, in any graph, a maximal independent set is also dominating.

Observation 2.21 (Folklore). Let W be a maximal independent set of a graph G. Then every vertex in V (G) \ W has at least one neighbour in W .

Dealing with the second case above is a bit more complicated, and this is particularly where we can take advantage of the fact that all vertices of G have the same (small) degree. In few words, the edge-weightings we design have the property that most edges incident to the vertices in H are assigned "small" weights, namely weights among {1, 2, 3}, while most edges incident to the vertices in W are assigned "big" weights, namely weights among {3, 4}. In other words, since all vertices of G have degree 5, we aim at sums for the vertices in H to be at most 3 × 5 = 15, while we aim at sums for the vertices in H to be at least 3 × 5 = 15. Following this approach, the only problem that might arise is when, for an edge uv of G with u ∈ H and v ∈ W , we get σ (u) = σ (v) = 15. This situation can actually be avoided through a careful case analysis.

Weighting bipartite graphs with two odd weights

As described in Section 2.1, an important problem related to neighbour-sum-distinguishing edge-weightings is to establish characterisations of graphs that can or cannot be weighted using a particular set of weights. When focusing on pairs of weights a, b, recall that, in general, there is, unless P=NP, no good characterisation of graphs having the {a, b}-property (Theorem 2.16). This is not true, however, for bipartite graphs and weights 1, 2, recall Theorem 2.10. As mentioned in Section 2.1.4, this result and others obtained by Lyngsie in [START_REF] Szabo Lyngsie | On neighbour sum-distinguishing {0, 1}-weightings of bipartite graphs[END_REF] suggest that, maybe, for any two a, b there is a good characterisation of bipartite graphs with the {a, b}-property.

Although they are far from covering all the cases of a and b, the previous series of results mentioned earlier show two things. First, that, when considering 2-connected bipartite graphs without the {a, b}-property, one should pay attention to odd multi-cacti. Second, that separable bipartite graphs without the {a, b}-property and those without the {a , b }-property may differ for different pairs {a, b} and {a , b }. This is well illustrated by nice trees: while they all have the {1, 2}-property (recall [START_REF] Chang | Vertex-coloring edge-weightings of graphs[END_REF]), infinitely many of them do not have the {0, 1}-property (recall [START_REF] Szabo Lyngsie | On neighbour sum-distinguishing {0, 1}-weightings of bipartite graphs[END_REF]).

In [START_REF] Bensmail | On {a, b}-edge-weightings of bipartite graphs with odd a, b[END_REF], we studied, in the context of bipartite graphs, the {a, b}-property when both a and b are odd. The main point is that cases where both weights are odd were covered by none of the previous studies on the topic. More precisely, we focused on the cases where b = a + 2, one of our main intentions being to focus even further on the case a = -1 and b = 1, which sounds very particular. Adapting, in this very context, mechanisms that are reminiscent to some used in the previous studies on the subject, one of the main results we got is that, for any odd a, 2-connected bipartite graphs without the {a, a+2}-property are precisely odd multi-cacti again. The proof of Theorem 2.22 is highly inspired from proofs in [START_REF] Szabo Lyngsie | On neighbour sum-distinguishing {0, 1}-weightings of bipartite graphs[END_REF] and [START_REF] Thomassen | The 3-flow conjecture, factors modulo k, and the 1-2-3-conjecture[END_REF] on the {1, 2}property and {0, 1}-property. The main difference, however, is that for these previous two properties, working with two weights of distinct parity is a very convenient thing for designing edge-weightings that are obviously neighbour-sum-distinguishing. In particular, with two weights of distinct parity a nice strategy is to make sure, for every edge uv, that σ (u) and σ (v) have distinct parity. Recall that this idea gives an easy way for showing that bipartite graphs with a partition class of even size have the {1, 2}-property (Observation 2.7). The exact same result with the exact same proof also holds for the {0, 1}-property.

Unfortunately, such arguments fail to work when a and b are both odd, because the walkswitching arguments (mentioned in the proof of Theorem 2.9) cannot be applied here. One of the most interesting parts in our proof of Theorem 2.22 is a way to make this work when b = a + 2 and a is odd. This is through the following concepts. A mod-4 vertex-colouring of a graph G is a vertex-colouring c : V (G) → {1, 2} of G satisfying the following conditions for any edge uv ∈ E(G) where d(u) and d(v) have the same parity:

1. If d(u) ≡ d(v) mod 4, then c(u) c(v). 2. If d(u) d(v) mod 4, then c(u) = c(v).
It turns out that every bipartite graph G admits a mod-4 vertex-colouring c. To convince the reader of this fact, let us point out that, in general, c might be far from fitting with the bipartition of G. Actually, G might have edges whose two ends have the same colour by c. Lemma 2.23. Every bipartite graph has a mod-4 vertex-colouring.

Lemma 2.23 can be proved easily by starting from an arbitrary 2-vertex-colouring c, and, while c does not meet the properties of a mod-4 vertex-colouring, moving vertices from a colour class to another one. Several arguments show that there are ways to perform this safely.

Let a, b ∈ Z be two odd integers with b = a + 2. Let G be a graph and X, Y be two disjoint subsets of its vertices. By an (X, Y )-a-parity {a, b}-edge-weighting of G, we mean an {a, b}-edgeweighting where all vertices in X are incident to an odd number of edges assigned weight a and all vertices in Y are incident to an even number of edges assigned weight a. (X, Y )-b-parity {a, b}-edge-weightings are defined similarly, but regarding incident edges assigned weight b. The following crucial lemma is the key for mimicking Observation 2.7 when we are using two weights a and b = a+2 with a odd. To make such a result work here, one must actually consider the colour classes by a mod-4 vertex-colouring, rather than those of the bipartition. If G has a mod-4 vertex-colouring where at least one of the two colour classes has even size, then G has the {a, b}-property. Consequently, if G does not have the {a, b}-property, then, in every mod-4 vertex-colouring, the two colour classes have odd size.

The proof of this crucial Lemma 2.24 is mostly by employing the walk-switching operation mentioned e.g. in the proof of Theorem 2.6. More precisely, we used the following refinement of a factor result introduced by Thomassen in [START_REF] Thomassen | Graph factors modulo k[END_REF]. Recall that, for a given graph G and mapping

f : V (G) → Z k , an f -factor modulo k is a spanning subgraph H of G such that, for every vertex v of G, we have d H (v) ≡ f (v) mod k. Lemma 2.25 ([75]). Let G be a connected graph. If f : V (G) → Z 2 is a mapping that satisfies v∈V (G) f (v) ≡ 0 mod 2, then G contains an f -factor modulo 2.
From this point on, the proofs from [START_REF] Szabo Lyngsie | On neighbour sum-distinguishing {0, 1}-weightings of bipartite graphs[END_REF] and [START_REF] Thomassen | The 3-flow conjecture, factors modulo k, and the 1-2-3-conjecture[END_REF] can be mimicked, but using mod-4 vertexcolourings (instead of the natural bipartition of the graph) and Lemma 2.24 (instead of Observation 2.7), to eventually lead to a proof of Theorem 2.22. In very rough words, the proof consists in analysing cuts (e.g. the cardinality of cut-sets, and how their removal disconnects the graph), and showing that, unless we are in the very peculiar case of an odd multi-cactus, there is a way to {a, a + 2}-edge-weight parts of the graph independently so that a neighboursum-distinguishing {a, a + 2}-edge-weighting of the whole graph results.

Similarly as for the {0, 1}-property, the structure of separable bipartite graphs without the {a, a + 2}-property for odd a does not appear obvious. So, in [START_REF] Bensmail | On {a, b}-edge-weightings of bipartite graphs with odd a, b[END_REF], we further focused on the case where a = -1, in order to get at least some insight into the matter. In that case, we can point out In the case of trees, when a, b are any two non-zero integers that are both positive (or negative), it is easy to see that K 2 is the only tree without the {a, b}-property: consider a vertex v whose all neighbours u 1 , . . . , u d-1 but one u d (if any) are leaves, remove u 1 , . . . , u d-1 , apply induction to deduce a neighbour sum-distinguishing {a, b}-edge-weighting, and extend the weighting to the edges vu 1 , . . . , vu d-1 so that all possible conflicts involving the ends of vu d are avoided. Thus, when b = a + 2 and a, b are odd, only the case a = -1, b = 1 is potentially non-trivial. This case is actually very particular for trees, as there exist infinitely many trees without the {-1, 1}-property. However, they are easy to construct, as they can all be constructed through the first operation above (illustrated in Figure 2.4, (a) and (b)) performed on K 2 's.

G 1 v 1 G 2 v 2 G 3 v 3 G 4 v 4 (a) Operation 1: Operands G 1 v 1 ∼ v 2 G 2 G 3 v 3 ∼ v 4 G 4 (b) Operation 1: Result G 1 v 1 G 2 v 2 (c) Operation 2: Operands G 1 v 1 G 2 v 2 (d) Operation 2: Result
Theorem 2.26. A tree does not have the {-1, 1}-property if and only if it can be constructed from a disjoint union of K 2 's through repeated applications of the first operation above.

Proving Theorem 2.26 can be done rather easily, by just studying structural properties of a minimal counterexample to the claim.

Results on side aspects

In this section, we investigate side aspects of the 1-2-3 Conjecture that would remain of interest even it that conjecture was shown true. We start off by investigating, in Section 2.3.1, the tradeoff between using weights with large value and generating a small number of distinct sums via a neighbour-sum-distinguishing edge-weighting. In Section 2.3.2, we then study the consequences on the 1-2-3 Conjecture of requiring a neighbour-sum-distinguishing edge-weighting to permit a more straight distinction of any two adjacent vertices. We finally consider, in Section 2.3.3, several ways of generalising the 1-2-3 Conjecture to digraphs.

The results from Section 2.3.1 were obtained jointly with Baudon, Hocquard, Senhaji and Sopena and appeared in [START_REF] Baudon | Edge Weights and Vertex Colours: Minimizing Sum Count[END_REF]. Those from Section 2.3.2 resulted in the article [START_REF] Baudon | Neighbour-Sum-2-Distinguishing Edge-Weightings: Doubling the 1-2-3 Conjecture[END_REF], and were obtained with Baudon, Senhaji and Sopena. The results from Section 2.3.3 were obtained with Barme, Przybyło and Woźniak, resulting in [START_REF] Barme | On a directed variation of the 1-2-3 and 1-2 Conjectures[END_REF], and with Lyngsie, resulting in [START_REF] Bensmail | 1-2-3 Conjecture in Digraphs: More Results and Directions[END_REF].

Minimising the number of obtained distinct sums

As mentioned in Section 2.1, a way to motivate neighbour-sum-distinguishing edge-weightings is that they can be regarded as a way to encode proper vertex-colourings. In particular, the 1-2-3 Conjecture states that, for every nice graph G, though a proper vertex-colouring might require up to ∆(G) + 1 colours, encoding one via the sums derived from an edge-weighting can be done by assigning the three weights 1, 2, 3 only.

One consequence, however, of using few weight values in a neighbour-sum-distinguishing edge-weighting ω of a graph G, is that the resulting proper vertex-colouring σ might be far from optimal, i.e., the number of distinct obtained sums might be larger than χ(G). Consider for instance the case of a locally irregular graph G. Clearly, χ e σ (G) = 1 (recall Observation 2.2); but the number of obtained distinct sums (colours by σ ) is exactly the number of distinct degree values over the vertices of G. Obviously, this number can be arbitrarily larger than χ(G) (consider, for instance, the case where G is bipartite).

When designing neighbour-sum-distinguishing edge-weightings, the only mattering point is that a proper vertex-colouring is produced, regardless of its quality (i.e., whether the number of resulting distinct sums is close to the chromatic number). It is however a legitimate question asking whether, via the sums inherited from a neighbour-sum-distinguishing edgeweighting, we can produce a proper vertex-colouring that is close to be optimal. Intuitively, the minimum number of distinct sums that can be obtained via a neighbour-sum-distinguishing edge-weighting is dependent of the edge weights we are allowed to use. There should thus be some trade-off between using a relatively large number of distinct edge weights and generating a relatively small number of distinct sums.

In [START_REF] Baudon | Edge Weights and Vertex Colours: Minimizing Sum Count[END_REF], we studied this aspect through a general parameter: For a given graph G and a set W of integers, we denote by γ W (G) the least number of distinct sums by a neighbour-sumdistinguishing W -edge-weighting of G (if any). As already mentioned, when γ W (G) is defined, we have χ(G) ≤ γ W (G); from this, two interesting and natural questions arise, namely How much larger than χ(G) can γ W (G) be? and For which sets W do we have γ W (G) = χ(G)? Due to the number of parameters (χ(G), W , G) involved in such questions, it seems tough providing ultimate answers. However, we managed to provide first-step answers to some of them.

Regarding sets of weights we can use to produce "optimal" neighbour-sum-distinguishing edge-weightings (i.e., with number of sums close to the chromatic number), we proved that the set Z of relative numbers is a good candidate. More precisely, we proved that for every nice graph G we have γ Z (G) = χ(G), except in one very peculiar case (recall that a bipartite graph is balanced if its two partition classes have the same cardinality).

Theorem 2.27. For every nice connected graph G, we have χ(G) ≤ γ Z (G) ≤ χ(G) + 1. Furthermore, the upper bound is attained if and only if G is a balanced bipartite graph. Theorem 2.27 was proved mainly through the walk-switching operation already mentioned in the proof of Theorem 2.6. The part of the statement dedicated to balanced bipartite graphs was obtained by contradiction, by carefully studying how a neighbour-sum-distinguishing Zedge-weighting should behave in such graphs if we want exactly χ(G) distinct sums to result.

When restricting weights to consecutive positive integers only, we provided both lower and upper bounds on the maximum value of γ {1,...,k} (G) for a given graph G, as functions of the maximum degree. These bounds are unfortunately rather general, and far from optimal, so we do not mind focusing further on them here. Let us however mention that, in the case of nice trees, we got a result that is somewhat optimal: Theorem 2.28. There are arbitrarily large values of ∆ for which

2 log 2 ∆ ≤ max tree T , ∆(T )=∆ γ {1,2} (T ) ≤ 2 log 2 (∆ -2) + 5.
The lower bound in Theorem 2.28 can be established by constructing trees having "many" adjacent vertices with close degree, to force them to have different sums by a neighbour-sumdistinguishing 2-edge-weighting. The upper bound was established by designing an algorithm for neighbour-sum-distinguishing 2-edge-weighting any tree in such a way that only a few number of sums can be generated. More precisely, for vertices with degree k, though the possible sums theoretically range in {k, . . . , 2k}, the algorithm works in such a way that only two values α k , β k in this set can be obtained as sums for degree-k vertices. Since vertices with close degree, say k and k , have intersecting ranges of possible sums, in such cases it is possible to choose α k , β k and α k , β k so that these values are the same. Using this idea, we proved that we can make the algorithm 2-edge-weight any nice tree in a neighbour-sum-distinguishing way so that the resulting sums are those among {α 1 , β 1 , α 2 , β 2 , . . . }, where the α i 's and β i 's are chosen so that this set includes a logarithmic number of values only.

The last result we established in [START_REF] Baudon | Edge Weights and Vertex Colours: Minimizing Sum Count[END_REF] is the NP-hardness of determining γ W . More precisely, we proved the NP-hardness of several decision problems arising when fixing some of the parameters involved in γ W . Our main result here states that, for a given bipartite graph G, determining whether γ {1,2} (G) ≤ k holds is NP-hard for every k ≥ 3. As a side result, we also established that finding the least k such that γ {1,...,k} (G) ≤ 3 holds is NP-hard for bipartite graphs G. The bipartite restriction is here important, as this forms a contrast with Theorem 2.4. That is, adding sum restrictions is sufficient to make problems related to neighboursum-distinguishing edge-weightings gain a level of complexity.

Distinguishing neighbours via larger sum differences

When designing neighbour-sum-distinguishing edge-weightings, the goal is to make adjacent vertices distinguishable via their incident sums. In ordinary neighbour-sum-distinguishing edge-weightings, adjacent vertices are considered distinguished as soon as their incident sums are distinct. In [START_REF] Baudon | Neighbour-Sum-2-Distinguishing Edge-Weightings: Doubling the 1-2-3 Conjecture[END_REF], we investigated edge-weightings that permit to distinguish the adjacent vertices in a stronger way. Namely, we require adjacent vertices to have incident sums differing by at least 2. This is what we call a neighbour-sum-2-distinguishing edge-weighting.

As can easily be observed, a neighbour-sum-distinguishing k-edge-weighting can be turned into a neighbour-sum-2-distinguishing 2k-edge-weighting by just multiplying all edge weights by 2. Moreover, since K 2 does clearly not admit any neighbour-sum-2-distinguishing edgeweighting, the notion of nice graphs for neighbour-sum-distinguishing edge-weightings and for neighbour-sum-2-distinguishing edge-weightings coincide. Again, we can thus wonder about the smallest k such that a given nice graph G admits a neighbour-sum-2-distinguishing k-edge-weighting, which we denote by χ e σ >1 (G). By the observation above, the 1-2-3 Conjecture, if true, would imply that χ e σ >1 (G) ≤ 6 holds for every nice graph G. One could thus wonder about a 1-2-3-4-5-6 Conjecture for neighboursum-2-distinguishing edge-weightings. It actually turns out that we did not manage to exhibit nice graphs G with χ e σ >1 (G) = 6. On the other hand, we proved that for several common classes of nice graphs G we have χ e σ >1 (G) ≤ 5. We were thus tempted to address the following. Conjecture 2.29. For every nice graph G, we have χ e σ >1 (G) ≤ 5. Note that Theorem 2.11 implies that χ e σ >1 (G) ≤ 10 holds for every nice graph G. Thus, even with the additional stronger sum requirement, the general bound we are interested in is indeed something constant. Through our investigations towards Conjecture 2.29, it seems that even the following refined conjecture might be true: Conjecture 2.30. Every nice graph admits a neighbour-sum-2-distinguishing {1, 3, 5}-edge-weighting.

In the context of neighbour-sum-2-distinguishing edge-weightings, Conjecture 2.30 might actually be an equivalent to the 1-2-3 Conjecture more natural than Conjecture 2.29. Indeed, in the 1-2-3 Conjecture we aim at getting incident sums differing by at least 1 through assigning three weights α -1, α, α + 1 differing by 1. In Conjecture 2.30, we aim at getting incident sums differing by at least 2 through assigning three weights β -2, β, β + 2 differing by 2.

Our results in [START_REF] Baudon | Neighbour-Sum-2-Distinguishing Edge-Weightings: Doubling the 1-2-3 Conjecture[END_REF] give evidence towards the previous two conjectures. The main result we got is that Conjecture 2.29 holds for nice bipartite graphs. To prove this, we again made use of the walk-switching operation described in the proof of Theorem 2.6. In order to understand the connection between Conjectures 2.29 and 2.30 better, we also gave a special focus to easy classes of bipartite graphs (paths, cycles, and odd multi-cacti). This additional investigation shows that, for some graphs G, the parameter χ e σ >1 (G) might be 2 or 4, and thus one should not only focus on Conjecture 2.30 when trying to determine χ e σ >1 (G) for a given graph G. We gave further support to this point by showing that it is NP-complete to determine whether χ e σ >1 (G) ≤ 2 holds for a given graph G. This statement remains true when restricted to bipartite graphs, which is yet another contrast with Theorem 2.4. However, we proved that this further distinction requirement is not sufficient to make the problem become hard for trees.

Generalising the conjecture to digraphs

A common direction for research is, given a graph problem defined on undirected graphs, to wonder about possible generalisations to digraphs. In the context of the 1-2-3 Conjecture, this does look as a promising direction for research. Indeed, by an arc-weighting of a digraph D, each vertex v gets associated two sums, σ -(v) and σ + (v), being the sum of weights on the arcs incoming and outgoing to and from v, respectively. So, there are two sum parameters to play with, from which we can come up with several options for defining a directed 1-2-3 Conjecture.

Generalising the conjecture to digraphs might seem a bit daring, as we are still far from understanding the original one, and digraph problems sometimes tend to be more complicated than their undirected counterparts. However, as will be shown in this section, we were unsuccessful in coming up with a challenging directed 1-2-3 Conjecture, despite several attempts.

To the best of our knowledge, only two directed variants of the 1-2-3 Conjecture have been introduced and studied prior to our considerations in this section. It was Borowiecki, Grytczuk and Pilśniak who first introduced an arc-weighting problem reminiscent of the 1-2-3 Conjecture [START_REF] Borowiecki | Coloring chip configurations on graphs and digraphs[END_REF]. In their arc-weighting notion, they consider two adjacent vertices u, v distinguished when |σ -(u)σ + (u)| |σ -(v)σ + (v)| holds, thus when their "relative sums" are different. They notably showed, via a simple proof, that all digraphs admit a 2-arc-weighting verifying this distinction condition for every arc. Later on, Khatirinejad, Naserasr, Newman, Seamone and Stevens proved, using the Combinatorial Nullstellensatz, that even the list version holds [START_REF] Khatirinejad | Digraphs are 2-weight choosable[END_REF].

During my Ph.D. studies, with Baudon and Sopena we later considered arc-weightings where every two adjacent vertices u, v are considered distinguished when σ + (u) σ + (v) holds, thus when their "outgoing sums" are different [START_REF] Baudon | An oriented version of the 1-2-3 Conjecture[END_REF]. We notably proved that every digraph can be 3-arc-weighted so that this distinction condition is verified for every arc (through an almost trivial inductive argument, to be recalled in the proof of Theorem 2.31 below), that a sort of list version of this result also holds, and that there is no good characterisation of digraphs admitting such distinguishing 2-arc-weightings (unless P=NP).

Just as in the previous variant, we believe it makes more sense, as first steps towards understanding directed variants of the 1-2-3 Conjecture, to focus on those arc-weightings where, for every arc --→ uv , one of the parameters σ -(u), σ + (u) is required to be different from one of the parameters σ -(v), σ + (v). In that spirit, to get a consistent terminology, we deal with the resulting variants of the 1-2-3 Conjecture through the following terminology. To each symbol α ∈ {-, +}, we associate a parameter:is associated to σ -while + is associated to σ + . Now, for two symbols α, β ∈ {-, +}, we say that an arc-weighting of a digraph D is (α, β)-distinguishing if, for every arc --→ uv of D, the parameter of u associated to α is different from the parameter of v associated to β. When writing χ α,β (D), we refer to the least k such that D admits (α, β)-distinguishing k-arc-weightings, if any. When referring to the (α, β) variant of the 1-2-3 Conjecture, we mean the variant involving (α, β)-distinguishing arc-weightings.

Note that this terminology allows to encapsulate four natural directed variants of the 1-2-3 Conjecture (with the (-, -) variant being identical to the (+, +) variant, up to reversing arc directions). Before going on, let us restate, in our new terminology, a result mentioned earlier. By the induction hypothesis, there is a (+, +)-distinguishing 3-arc-weighting of D , which we wish to extend to the arcs outgoing from v. Recall that weighting such an arc affects σ + (v) only, so we only need to make sure that the arcs outgoing from v are weighted so that σ + (v) is involved in no conflict. Since we are using weights 1, 2, 3, the possible sums as σ + (v) are those in S = {d + (v), . . . , 3d + (v)}, which is a set of 2d + (v)+1 values. By our choice of v, the number of neighbours of v is at most 2d + (v). Thus, there is a value α in S which does not appear as the outgoing sum of a neighbour of v. We then obtain a (+, +)-distinguishing 3-arc-weighting of D when weighting the arcs outgoing from v so that σ + (v) = α.

In the rest of this section, we investigate the two remaining directed variants of the 1-2-3 Conjecture, namely the (+, -) variant and the (-, +) variant. Just as for the (+, +) variant, we completely solve these two variants.

The (+, -) variant

Recall that, in the (+, -) variant of the 1-2-3 Conjecture, one aims at designing arc-weightings verifying σ + (u) σ -(v) for every arc --→ uv . Out of the four natural directed variants of the 1-2-3 Conjecture we are considering in this section, this variant might at first glance seem the closest to the original conjecture, as this is the only one where weighting an arc --→ uv directly affects the two parameters (σ + (u) and σ -(v)) that are required to differ for the two ends u, v.

First, it is worth mentioning that not all digraphs admit (+, -)-distinguishing arc-weightings. To be convinced of this statement, just consider a digraph D having an arc --→ uv such that d + (u) = d -(v) = 1. Then, no matter what weight α is assigned to --→ uv , clearly we get σ + (u) = σ -(v) = α; so there is no hope to find a (+, -)-distinguishing arc-weighting. However, one can easily check that if D is nice, in the sense that it does not admit such a lonely arc, then D admits a (+, -)-distinguishing arc-weighting (just consider sufficiently fast increasing weights, just as one would prove Observation 2.1).

There exist nice digraphs admitting no (+, -)-distinguishing 2-arc-weightings. One easy family of digraphs for which the parameter χ +,-is 3 is squares of odd-length cycles in which the two Hamiltonian cycles are directed to form two directed cycles (see Figure 2.5). Assume indeed we assign weights 1 and 2 only in such a digraph. Such a digraph is 2-regular and weighting, say, 1 an arc, say, ----→ v 1 v 2 forces the weights of the second arc outgoing from v 1 and of the second arc incoming to v 2 to be different (so that σ + (v 1 ) σ -(v 2 )). Repeating this argument until all arcs are weighted following successive deductions, eventually we reach a contradiction. So, such a digraph can only be weighted with at least three weights. Our results in this section will actually clarify why such digraphs cannot be weighted with 1 and 2.

We were not able to find nice digraphs D for which we have χ +,-(D) > 3. So we felt confident in raising the following conjecture, which stands as a straight analogue of the 1-2-3 Conjecture: ----→ v 2 v 1 weighted 1 (a) forces two adjacent arcs to be weighted differently (b). By then repeatedly considering a weighted arc ---→ v i v j such that the second arc outgoing from v i is weighted while the second arc incoming to v j is not, or vice versa, we deduce that another arc adjacent to ---→ v i v j has its weight forced so that σ + (v i ) σ -(v j ) ((c) to (g)). The deduction process here ends up with σ + (v 6 ) = σ -(v 4 ) regardless of the weight of ----→ v 6 v 4 , a contradiction. Surprisingly enough, there is actually an easy way to fully prove that Conjecture 2.32 holds true, which relies on the following equivalence:

Theorem 2.33. The following two problems are equivalent:

(1) Conjecture 2.32 for nice digraphs.

(2) The 1-2-3 Conjecture for nice bipartite graphs.

Since the 1-2-3 Conjecture holds for nice bipartite graphs, recall Theorem 2.9, from Theorem 2.33 we get that χ +,-(D) ≤ 3 holds for every nice digraph D. Because the proof of Theorem 2.33 is actually rather easy and somewhat surprising, let us give a few details about it. For that, we first need to introduce some notation and terminology. Let G be a bipartite graph with bipartition A ∪ B. In the following, we say that G is anti-matchable if G is balanced and its complement has a perfect matching across A and B. Said differently, G is anti-matchable if it is balanced and has a set of disjoint non-edges between A and B covering all the vertices. Assuming the vertices in A and B are explicitly ordered, i.e., from first to last, we call G anti-matched if, for every i ∈ {1, . . . , |A|}, the ith vertex of A is not adjacent to the ith vertex of B. Now consider a digraph D with vertices v 1 , . . . , v n . The bipartite graph B(D) associated to D is the (undirected) bipartite graph B(D) with bipartition V + ∪ V -constructed from D as follows:

• For every vertex v i of D, add a vertex v + i to V + , as well as a vertex v - i to V -.

• For every arc ---→ v i v j of D, add the edge v + i v - j to B(D).

Note that B(D) is anti-matched. This construction is illustrated in Figure 2.6. The other direction of the equivalence follows from the fact that for every nice bipartite graph G, we can construct a nice digraph D that is equivalent in terms of weighting, i.e. verifying G = B(D). This can be done in particular by adding dummy isolated vertices to G to ensure this graph is balanced and anti-matchable. The arguments above then apply. Theorem 2.33 is rather unexpected: although the (+, -) variant of the 1-2-3 Conjecture seemed like a challenging problem at first, it is in fact as complicated as a particular case of the 1-2-3 Conjecture, which is actually one of the cases we understand the most.

v 1 v 2 v 3 v 4 v 5 v 6 v 7 (a) v + 1 v + 2 v + 3 v + 4 v + 5 v + 6 v + 7 v - 1 v - 2 v - 3 v - 4 v - 5 v - 6 v - 7 (b)
Note that the notion of associated bipartite graph also explains why there exist digraphs This implies that there is an easy characterisation of digraphs D with χ +,-(D) = 3.

D

The (-, +) variant

The last one of the four directed variants of the 1-2-3 Conjecture that can be defined over the single parameters σ -and σ + , is the (-, +) variant. Note that this variant has a general behaviour that is rather distant from one of the original 1-2-3 Conjecture; that is, weighting an arc --→ uv affects σ + (u) and σ -(v) which play no role in the distinction condition that u and v must fulfil.

The (-, +) variant of the 1-2-3 Conjecture was first considered in 2018 by Horňák, Przybyło and Woźniak [START_REF] Horňák | A note on a directed version of the 1-2-3 Conjecture[END_REF]. They first noticed that χ -,+ (D) is not defined for digraphs having an arc --→ uv such that u is a source and v is a sink (since we would always have σ -(u) = σ + (v) = 0). Such an arc is called an ss-arc. For digraphs with no ss-arcs, it can be checked that, again, the parameter χ -,+ is now defined (using inductive arguments, which are easy to apply when the weights are not bounded). However, for digraphs with no ss-arcs, the parameter χ -,+ is not bounded by an absolute constant, but this can only be due to the presence of lonely arcs. Indeed, lonely arcs yield vertices v where either σ -(v) or σ + (v) is determined by the weight of a unique incident arc. One can then build digraphs with many lonely arcs forming a kind of clique, which forces them to be assigned pairwise distinct weights by any (-, +)-distinguishing arc-weighting.

Regarding this (-, +) variant of the 1-2-3 Conjecture, a digraph is said nice whenever it has neither ss-arcs nor lonely arcs; this terms makes sense because the parameter χ -,+ is bounded by a constant for digraphs without such bad configurations. As a support to Conjecture 2.36, Horňák, Przybyło and Woźniak proved it for several families of digraphs, including tournaments and symmetric digraphs.

In [START_REF] Bensmail | 1-2-3 Conjecture in Digraphs: More Results and Directions[END_REF], with Lyngsie we provided more results towards understanding this (-, +) variant. The first result we provided is a proof of Conjecture 2.36. To prove the bound of 4 in Theorem 2.35, Horňák, Przybyło and Woźniak, in [START_REF] Horňák | A note on a directed version of the 1-2-3 Conjecture[END_REF], made use of the relationship between graph weighting and digraph weighting established through associated bipartite graphs, described earlier in the proof of Theorem 2.33 for the (+, -) variant. For the (-, +) variant, however, we note that this relation is a bit off. Indeed, consider a digraph D and its associated bipartite graph B(D). For every arc --→ uv of D, we have a corresponding edge u + v -in B(D). In a neighboursum-distinguishing edge-weighting of B(D), we do require σ (u + ) to be different from σ (v -), which is not representative of what we require in a (-, +)-distinguishing arc-weighting of D, namely that σ -(u) gets different from σ + (v). In B(D), it is actually probable that σ (u -) gets equal to σ (v + ), as u -and v + might not be adjacent. The crucial point is that edge-weighting B(D) gives an arc-weighting of D that is equivalent in terms of obtained sums; however, it is not equivalent in terms of sum constraints, because, from the point of view of the constraints, the structure of B(D) is not representative of that of D.

To overcome this point, Horňák, Przybyło and Woźniak build neighbour-sum-distinguishing 4-edge-weightings of B(D) that, when derived to D, yield (-, +)-distinguishing arc-weightings no matter what the sum constraints actually are. To that aim, they weight B(D) so that the σ (v + )'s are different from all the σ (v -)'s; this way, back in D, this yields an arc-weighting where the σ + (v)'s are different from the σ -(v)'s. This is done by making sure the incident sums range in two disjoint sets. And, to achieve this, they use weights 1, 2, 3, 4.

We proved Conjecture 2.36 through the same ideas, with a more refined analysis. Our proof is actually a consequence of the following result: Theorem 2.37. Every nice connected bipartite graph G with bipartition U ∪V has a neighbour-sumdistinguishing 3-edge-weighting ω where:

• for every u ∈ U , we have σ (u) ∈ U and

• for every v ∈ V , we have σ (v) ∈ V , for • U = {0, 3} ∪ {3k + 1 : k ≥ 1} and • V = {0, 1, 2} ∪ {3k -1, 3k : k ≥ 2}.
To make it clearer, we have U = {0, 3, 4, 7, 10, 13, 16, . . . } and V = {0, 1, 2, 5, 6, 8, 9, 11, 12, 14, 15, . . . }.

The value 0 in both U and V is to catch vertices with degree 0, which can occur in associated bipartite graphs. We note that the sets U and V are quite restrictive. Notably, for every vertex u ∈ U with d(u) = 1, its unique incident edge must be weighted 3. However, the sums in U and V that must be reached for vertices become more "regular" as soon as the degree is large enough. For instance, every vertex with degree at least 4 cannot have sum in {1, 2, 3} which are the peculiar values of the sets U and V . The proof of Theorem 2.37 builds upon simple ideas. Consider a "root" vertex r of G, and the natural layering

V 0 ∪ V 1 ∪ • • • ∪ V d of
G we then get, where each V i contains the vertices at distance i from r. Then repeatedly consider the vertices from "bottom to top" (i.e., start with those in V d , then continue with those in V d-1 , etc.), and, for every such considered vertex v r, weight its edges going upwards (i.e., to the previous upper level; there is at least one such edge) so that σ (v) lies in the corresponding one of U or V . It is easy to see that this can always be achieved with using weights 1, 2, 3, because any two consecutive values in U and V are distant by at most 3. Achieving this for all vertices in V 1 , . . . , V d , we get a weighting of the whole of G, which guarantees the desired sum condition for all vertices of G but maybe r. If σ (r) also lies in the corresponding one of U or V , then we are done. Otherwise, the rest of the proof consists in showing that for many edges there are actually multiple choices that can be repercuted all the way up to the edges incident to r, and that the resulting multiple choices incident to r are enough to guarantee a sum as σ (r) which is as desired. These choices might result from multiple sources, for instance the fact that a vertex v r has multiple edges going upwards, or that v ∈ V and v is a degree-1 vertex. An important fact also is that U and V include two small values which differ by 1 only; this is crucial for guaranteeing that, also for vertices with small degree (thus with only a few incident edges going upwards), we have sum choices, if needed.

A nice anecdotal fact to mention is that we came up with the sets U and V after many intensive experimentations via computer programs in order to find possible counterexamples to Conjecture 2.36. Another nice aspect is that Theorem 2.37 is again strongly related to the undirected context, in particular to the 1-2-3 Conjecture for bipartite graphs, just as the (+, -) variant, which is sort of unexpected due to the quite different behaviours of the (-, +) variant.

As another result on the (-, +) variant in [START_REF] Bensmail | 1-2-3 Conjecture in Digraphs: More Results and Directions[END_REF], we proved that there is no good characterisation of nice digraphs D with χ -,+ (D) ≤ 2, unless P=NP.

Conclusion and perspectives

Summary of the contributions in the chapter

In this chapter, we have surveyed results of more or less importance towards understanding several aspects of the 1-2-3 Conjecture. The most important result of the chapter is certainly Theorem 2.18, because there are not, to date, that many classes of graphs for which we know how to do better than Theorem 2.11, the best result we have in this context. An interesting fact also is that Theorem 2.18 is based on enhancing Kalkowski's Algorithm (the key behind Theorem 2.11) with new features. Regarding Theorem 2.22, though the proof is quite reminiscent of those in [START_REF] Szabo Lyngsie | On neighbour sum-distinguishing {0, 1}-weightings of bipartite graphs[END_REF] and [START_REF] Thomassen | The 3-flow conjecture, factors modulo k, and the 1-2-3-conjecture[END_REF], the nicest thing here is the way (Lemma 2.24) we found to replace Observation 2.7 when two odd weights are used. Although this is rather expected, Theorem 2.22 is yet another evidence that, when {a, b}-edge-weighting nice bipartite graphs in a neighbour-sum-distinguishing way, one should pay a special attention to odd multi-cacti.

The side aspects of the 1-2-3 Conjecture we have investigated led to questions which are, in my opinion, interesting to consider towards going beyond the 1-2-3 Conjecture, and understanding the deepest aspects of neighbour-sum-distinguishing edge-weightings. In particular, the results from Section 2.3.1 establish some connection between neighbour-sum-distinguishing edge-weightings and the proper vertex-colourings they encode. The results from Section 2.3.2 show the real importance of the weights 1, 2, 3 in the 1-2-3 Conjecture. These two series of results show another interesting thing also. Namely, due to Theorem 2.10, we know that it can be decided in polynomial time whether a given bipartite graph can be 2-edge-weighted in a neighbour-sum-distinguishing way. The interesting thing is that some of the results mentioned in Sections 2.3.1 and 2.3.2 show that under mild additional requirements (minimising the number of sums and making the adjacent vertices distinguishable in a stronger way, respectively), this problem becomes NP-hard. This is of interest as, as highlighted throughout this chapter, bipartite graphs are, to date, among the most investigated classes of graphs in the context of the 1-2-3 Conjecture and related problems.

Another side aspect we have considered in Section 2.3.3 is generalising the 1-2-3 Conjecture to digraphs. The presented results are, in my opinion, quite intriguing, as they mainly show that the 1-2-3 Conjecture might be one of these problems that become much easier when going to digraphs. Note, in particular, that the four natural directed variants we have introduced are totally understood, from both the combinatorial point of view and algorithmic point of view. Something interesting, however, is that these four variants show some different behaviours. In particular, the notion of nice digraphs varies from a variant to another: no configuration is bad for the (+, +) and (-, -) variants, lonely arcs are bad for the (+, -) variant, and both ss-arcs and lonely arcs are bad for the (-, +) variant. The proofs developed to prove these directed variants of the 1-2-3 Conjecture are also of varying complexity: an almost trivial inductive argument for the (+, +) and (-, -) variants (Theorem 2.31), an equivalence with the 1-2-3 Conjecture in bipartite graphs for the (+, -) variant (Theorem 2.33), and a stronger result on neighbour-sumdistinguishing 3-edge-weightings in bipartite graphs for the (-, +) variant (Theorem 2.37). This is also yet another context where neighbour-sum-distinguishing edge-weightings of bipartite graphs arise, giving yet more weight to this class of graphs for the 1-2-3 Conjecture.

Recent results and developments

The ideas we have developed for proving Theorem 2.18 opened the way for proving more results on the topic, some of which are rather important. With Przybyło, we combined these ideas with probabilistic arguments in [START_REF] Bensmail | Decomposability of graphs into subgraphs fulfilling the 1-2-3 Conjecture[END_REF] to get results to be mentioned in Chapter 3. By refining these ideas further, Przybyło also managed to get important progress towards the 1-2-3 Conjecture by generalising Theorem 2.18 for all nice regular graphs in [START_REF]The 1-2-3 Conjecture almost holds for regular graphs[END_REF]. In other words, he improved Theorem 2.11 to a 1-2-3-4 result for all nice regular graphs. This is a big step, as, in some sense, regular graphs are (intuitively, to the least) among the most complicated graphs for the 1-2-3 Conjecture (since all their vertices share the same range of possible sums by an edge-weighting, and therefore a sum conflict can arise along any edge).

A number of other results improving the bound in Theorem 2.11, at least for particular classes of graphs, have also appeared in literature. Two such results of interest are the verification of the 1-2-3 Conjecture for dense graphs (being unions of cliques) by Zhong [START_REF] Zhong | The 1-2-3-conjecture holds for dense graphs[END_REF], and for 4-edge-connected graphs with chromatic number at most 4 by Wu, Zhang and Zhu [START_REF] Wu | Vertex-coloring 3-edge-weighting of some graphs[END_REF]. The latter result is of interest as it goes a bit beyond Theorem 2.6, and nice 3-colourable graphs are essentially the largest class of graphs for which the 1-2-3 Conjecture was verified. A point also lies in the proof of that result, which makes use of edge-disjoint spanning trees that are guaranteed to exist due to the edge-connectivity condition.

There have also been in literature a few other works dedicated to understanding the true importance of the weight 1, 2, 3 in the 1-2-3 Conjecture. One first such is [START_REF] Baudon | Equitable neighbour-sum-distinguishing edge and total colourings[END_REF], in which Baudon, Pilśniak, Przybyło, Senhaji, Sopena and Woźniak introduced and studied equitable neighboursum-distinguishing edge-weightings, where the difference with regular ones is that every two weight values must be assigned about the same number of times (i.e., for every two weight values a, b, it is required that the number of occurrences of a's and the number of occurrences of b's differ by at most 1). This is a nice aspect to consider in my opinion, as equitability is a way to force the use of all weight values, while, in general, not being forced to fulfil such an equitability requirement leads to designing neighbour-sum-distinguishing edge-weightings that are very unbalanced in terms of weight occurrences. For instance, the proof of Theorem 2.5, though very simple, describes edge-weightings where weight 2 is assigned only once. Also, there is an easy way, via employing Observation 2.7, to prove that odd multi-cacti admit neighbour-sum-distinguishing 3-edge-weightings assigning weight 3 at most twice.

The results from [START_REF] Baudon | Equitable neighbour-sum-distinguishing edge and total colourings[END_REF] mostly established that, for most nice graphs G in some easy classes (trees, complete graphs, etc.), the equitability condition does not increase the number of weight values needed to weight G. That is, it seems that, in general, any nice graph G admits equitable neighbour-sum-distinguishing χ e σ (G)-edge-weightings. Although this would sound even more intriguing, it would thus make sense wondering about an equitable 1-2-3 Conjecture.

A missing result from [START_REF] Baudon | Equitable neighbour-sum-distinguishing edge and total colourings[END_REF], however, was a reasonable bound k such that every nice graph G admits an equitable neighbour-sum-distinguishing k-edge-weighting. To get some progress towards this, with Senhaji and Lyngsie we introduced in [START_REF] Bensmail | On a combination of the 1-2-3 Conjecture and the Antimagic Labelling Conjecture[END_REF] the stronger notion of edge-injective neighbour-sum-distinguishing edge-weightings, which are neighbour-sum-distinguishing edgeweightings where no two edges are assigned the same weight. Note that every edge-injective neighbour-sum-distinguishing edge-weighting is indeed equitable. A conjecture we raised (and that we supported with some partial results) is that there should be a way to weight every nice graph G with 1, . . . , |E(G)| so that an edge-injective neighbour-sum-distinguishing edge-weighting results. As stated earlier, if true, our conjecture would give a linear bound (in the number of edges) towards an equitable 1-2-3 Conjecture. An interesting side fact is that our conjecture stands as a local version of the Antimagic Labelling Conjecture (introduced by Hartsfield and Ringel in [START_REF] Hartsfield | Pearls in Graph Theory[END_REF]), which states that such an edge-weighting should exist even if one requires σ (u) σ (v) for every two distinct vertices u, v (even if uv is not an edge). Our conjecture was later proved independently by Haslegrave [START_REF] Haslegrave | Proof of a local antimagic conjecture[END_REF] and Lyngsie and Zhong [START_REF] Szabo Lyngsie | A Generalized Version of a Local Antimagic Labelling Conjecture[END_REF]. Still, it was sort of nice starting from a problem derived from the 1-2-3 Conjecture, and unexpectedly ending up with some weakening of another important problem of the field.

Another big result in the recent years is by Vučković, who, in [START_REF] Vučković | Multi-set neighbor distinguishing 3-edge coloring[END_REF], proved the multiset version of the 1-2-3 Conjecture, or, in other words, Conjecture 2.12. His proof of this is more tedious than sophisticated, as it is mainly based on studying the edges between the colour classes of a proper vertex-colouring, and taking advantage of the fact that if the chromatic number is large (which can be assumed to be at least 4, as Theorems 2.6 and 2.9 apply for smaller values), then many vertices are incident to a lot of edges. This is quite in the spirit of the older proof schemes through which the first upper bounds towards the 1-2-3 Conjecture were established; from that point of view, I think the proof of the 1-2-3-4 result from [START_REF] Addario-Berry | Vertex colouring edge partitions[END_REF] remains much more interesting.

Perspectives for future work

The ultimate perspective for research here is of course to prove the 1-2-3 Conjecture, which remains out of reach at the moment. Still, there is some hope due to recent proof schemes and techniques, such as the spanning trees one from [START_REF] Wu | Vertex-coloring 3-edge-weighting of some graphs[END_REF] or the way we have proved Theorem 2.18 (which already led to further understanding of the conjecture), and also due to recent results that are getting very close, such as Theorem 2.14 or the multiset result of Vučković in [START_REF] Vučković | Multi-set neighbor distinguishing 3-edge coloring[END_REF]. I am also firmly convinced that the next big thing to exploit to get further progress is methods based on algebraic tools. Indeed, the 1-2-3 Conjecture is actually nothing but a purely algebraic problem, and it seems natural attacking it from that angle. At the moment we are still missing some dedicated tools, but I am pretty sure that continuing bringing ones from close fields, such as Alon's Combinatorial Nullstellensatz [START_REF] Alon | Combinatorial Nullstellensatz[END_REF], in this context is the way to go.

There are many more doable things that might be interesting to consider first in the near future. For instance, it would be interesting to prove more 1-2-3-4 results, in the flavour of Theorem 2.18 and its generalisation by Przybyło in [START_REF]The 1-2-3 Conjecture almost holds for regular graphs[END_REF]. To that aim, it would be interesting to see how the concepts in our proof of Theorem 2.18 can be pushed in the context of other graph classes. Recall that, in that proof, it is important that the considered graph has a dominating independent set with particular properties. Perhaps something can be said for e.g. graphs with a universal vertex, chordal graphs, etc., which are graphs that are particular in that regard.

Regarding proving the original statement of the 1-2-3 Conjecture for more classes of graphs, the next natural step would be to do so for 4-chromatic graphs. Recall that the result of Wu, Zhang and Zhu in [START_REF] Wu | Vertex-coloring 3-edge-weighting of some graphs[END_REF] already goes in that direction, and the type of arguments used there might be the key for going farther. In particular, it might be interesting to investigate a proof of the 1-2-3 Conjecture for planar graphs, which is still not something yet.

Lastly, let us mention that it might be very interesting studying whether the multiset result of Vučković in [START_REF] Vučković | Multi-set neighbor distinguishing 3-edge coloring[END_REF] and its proof can be generalised to more variants of the 1-2-3 Conjecture. In particular, can something be done about the product version of the 1-2-3 Conjecture? The main difference between that version and the 1-2-3 Conjecture is that we now compute, at each vertex, the product of incident weights. This version was mostly studied by Skowronek-Kaziów (see [START_REF] Skowronek-Kaziów | Multiplicative vertex-colouring weightings of graphs[END_REF] for its introduction), and we purposely did not mention it in Section 2.1 because the author mainly adapts existing results in this context without properly pointing out these connections. For instance, note that assigning weights 1, 2 only in the product version is similar to assigning weights 0, 1 only in the sum version. Also, assigning 1, 2, 3 only in the product version is similar to assigning weights 2, 3 and a "neutral element" in the multiset version. From these arguments, it is not complicated to see that many existing results on the sum and multiset versions translate to the product version. In particular, in her seminal work, Skowronek-Kaziów proved that, in the product version, every nice graph can be weighted with 1, 2, 3, 4, using the exact same proof scheme as for the multiset version in [START_REF] Addario-Berry | Vertex colouring edge partitions[END_REF]. Now that Conjecture 2.12 was proved by Vučković, due to these connections it would be interesting to check whether his proof scheme can lead to a proof of the product version of the 1-2-3 Conjecture.

The three side aspects we have considered in Section 2.3 also lead to open questions and ways of generalisation that might be interesting to consider further. What we have investigated in Section 2.3.1 is perhaps the most interesting one due to its connection with proper vertexcolourings, which is a central notion in graph theory. A way to get some sort of progress here is by noting that the minimum possible number of distinct sums by a neighbour-sumdistinguishing k-edge-weighting is bounded above by the minimum maximum vertex sum we can generate by a neighbour-sum-distinguishing k-edge-weighting. Noticing this connection, we recently studied this aspect in [START_REF] Bensmail | On Minimizing the Maximum Color for the 1-2-3 Conjecture[END_REF] with Li, Li and Nisse. In that work, we have established several combinatorial and algorithmic results related to these concerns. In particular, a general conjecture we have is that every nice graph G should admit a neighbour-sum-distinguishing edge-weighting where the maximum sum is at most 2∆(G). What I particularly like here, is that this is a way to turn concerns about the 1-2-3 Conjecture into an optimisation problem, which leads to new types of questions that we are normally not used to consider in this context.

Regarding our investigations in Section 2.3.2, it would be interesting to study, more generally, what weights are required to weight a nice graph so that any two adjacent vertices have their sums differing by a larger fixed amount, say d. In a sense, this is similar to asking the adjacent vertices to be even more distinguishable by an edge-weighting. Following the observations we made, a legitimate generalisation of the 1-2-3 Conjecture, which we raised in [START_REF] Baudon | Neighbour-Sum-2-Distinguishing Edge-Weightings: Doubling the 1-2-3 Conjecture[END_REF], is that maybe weights 1, d + 1, 2d + 1, i.e., three weights every two successive of which differ by d, permit to weight all nice graphs in this stronger manner.

Finally, regarding our investigations in Section 2.3.3, we are still missing a directed variant of the 1-2-3 Conjecture that would perfectly mimic its behaviours, and would be seemingly as challenging to prove. We have here investigated generalisations where any two adjacent vertices u, v should be distinguishable following one of the parameters σ -(u), σ + (u) of u and one of the parameters σ -(v), σ + (v) of v. Perhaps the way to go, just as in [START_REF] Borowiecki | Coloring chip configurations on graphs and digraphs[END_REF], would now be to play with combinations or functions of these parameters.

Chapter 3

Locally irregular decompositions

In this chapter, I describe the works I have been conducting towards understanding locally irregular graphs and locally irregular decompositions better. The main point for studying these two notions is that they have shown, over the years, to have strong connections to the 1-2-3 Conjecture, as they popped out naturally through numerous investigations on the topic. In particular, locally irregular graphs and decompositions stand as fundamental notions to understand in this context, as they are the key establishing the very decompositional nature of the 1-2-3 Conjecture. Since their formal introduction, they have also been studied, out of this context, as separate objects carrying their own independent interest.

Locally irregular decompositions, which we define thoroughly below, are a notion we have first introduced and studied with Baudon, Przybyło and Woźniak during my Ph.D. studies, resulting in [START_REF] Baudon | On decomposing regular graphs into locally irregular subgraphs[END_REF]. The main point, given a graph G, is to determine its irregular chromatic index χ irr (G), which is the least number of parts in a locally irregular decomposition of G (if any). Section 3.1 below is dedicated to recalling the formal definitions and results we got in the seminal work [START_REF] Baudon | On decomposing regular graphs into locally irregular subgraphs[END_REF] on the irregular chromatic index of graphs. In particular, we recall Conjecture 3.3, which states that there should be a general constant bounding the irregular chromatic index, which will be our guiding thread throughout this chapter. The next sections then describe the development of my research following that thread; in particular:

• In Section 3.2 are described the most notable progresses I made over the years towards Conjecture 3.3. This section features results establishing the first constant bound on the irregular chromatic index, and improved bounds for degenerate graphs.

• In Section 3.3 is then described an attempt to establish the real fundamental connection between the 1-2-3 Conjecture and locally irregular decompositions. This emerged in a general decomposition problem, Conjecture 3.30, enclosing both the 1-2-3 Conjecture and Conjecture 3.3, which relates to most of the results of the field.

Introduction

Recall that, in previous Chapter 2, we already ran into locally irregular graphs, which are graphs in which no two adjacent vertices have the same degree (see Figure 3.1 for an illustration). As mentioned earlier, locally irregular graphs appeared naturally during several investigations towards the 1-2-3 Conjecture over the years. For instance, locally irregular graphs are precisely at the heart of the first motivation we have given for studying neighbour-sum-distinguishing edge-weightings (Solution 1 given at the beginning of Section 2.1), while they are explicitly mentioned in [START_REF] Addario-Berry | Degree constrained subgraphs[END_REF] as the authors proved that χ e σ (G) ≤ 16 holds for every nice graph G. Also, locally irregular graphs are precisely those graphs G with χ e σ (G) = 1, recall Observation 2.2. When a graph G is not locally irregular, it might be convenient to decompose it into locally irregular graphs. By a decomposition of G, we mean a partition

E 1 ∪ • • • ∪ E k of E(G). A locally irregular decomposition of G is then a decomposition E 1 ∪ • • • ∪ E k where G[E i ]
is locally irregular for every i ∈ {1, . . . , k}. Note that locally irregular decompositions can equivalently be seen as edge-colourings where each colour class yields a locally irregular graph. We will thus say that an (improper) edge-colouring of G is locally irregular if it forms a locally irregular decomposition. Refer to Figure 3 Just as locally irregular graphs, locally irregular decompositions arise when studying specific aspects of the 1-2-3 Conjecture. Given that a graph G is not locally irregular, one natural approach to prove it verifies the 1-2-3 Conjecture could be to first decompose G into locally irregular graphs, which are graphs that are "easy" for the 1-2-3 Conjecture (i.e., each locally irregular graph H verifies χ e σ (H) = 1), and weight their edges independently in some fashion. In more specific contexts, locally irregular decompositions actually arise naturally, just as in Observation 2.15. The situation described in that observation is actually not that anecdotal as we still do not know if, in general, regular graphs verify the 1-2-3 Conjecture. In a sense, Observation 2.15 provides another way of interpreting Theorem 2.16.

Observation 2.15 is an example of a case where, given a graph G that is not locally irregular, we would be interested in having a decomposition of it into a "limited" number of locally irregular graphs. As locally irregular decompositions and locally irregular edge-colourings are similar objects, for G we denote by χ irr (G) the least number of colours in a locally irregular edge-colouring of G, if any. We call this parameter χ irr (G) the irregular chromatic index of G. In a way, the irregular chromatic index is a measure of how far from locally irregular a graph is.

This parameter was introduced and first studied during my Ph.D. studies. Before focusing on investigating whether graphs can have large irregular chromatic index or not, a first task was to determine which are the graphs we are dealing with. Indeed, not all graphs are decomposable, in the sense that they have finite irregular chromatic index. There are actually some exceptional graphs, or exceptions, which are graphs that cannot be decomposed into locally irregular subgraphs at all. K 2 is again a pathological case of an exceptional graph, but it is easy to see that also many paths and cycles are exceptional. More precisely, because the only connected locally irregular graph G with ∆(G) ≤ 2 is the path of length 2, the following holds: Observation 3.1. Paths and cycles of odd length are not decomposable.

There is actually a third class T of connected exceptions. The definition of T is recursive:

u w v Figure 3.3:
Iterative construction of a member of T . The construction starts e.g. from the triangle uvwu with green edges. An even-length pending path with magenta edges is then attached to u. To v is then attached an odd-length path with cyan edges at the other end of which is attached a triangle with purple edges. To w is finally attached an odd-length path with blue edges at the other end of which is attached a triangle with red edges. Every graph obtained after some of these successive steps is also a member of T .

2. Every other graph in T can be constructed by 1) taking an auxiliary graph H being either an even-length path or an odd-length path with a triangle glued to one of its ends, then 2) choosing a graph G ∈ T containing a triangle with at least one vertex, say v, of degree 2 in G, and finally 3) identifying v with a vertex of degree 1 of H.

See Figure 3.3 for an example displaying several members of T . The graphs in T consist of disjoint triangles connected in a tree-like fashion, such that, when contracting the triangles to vertices, two consecutive "triangle vertices" are joined by an odd-length path, while a "triangle vertex" and a consecutive original degree-1 vertex are joined by an even-length path. Following that description, it should be clear that these graphs are easy to recognise.

We have proved in [START_REF] Baudon | On decomposing regular graphs into locally irregular subgraphs[END_REF] that the members of T are also not decomposable, through straight inductive arguments. Furthermore, through a study of the structural properties of exceptional graphs, we have shown that the union of all odd-length paths, odd-length cycles and members of T is exactly the class of connected exceptional graphs.

Theorem 3.2 ([17]). A connected graph is not decomposable if and only if it is an odd-length path, an odd-length cycle, or a member of T .

It is worth emphasising that all connected exceptions have odd size, maximum degree at most 3, low degeneracy (at most 2), and are planar. Thus these graphs are rather common, which, as will be pointed out all along this chapter, is a troublesome point. Now that the class of graphs that are not decomposable is clear, we are ready to state our main conjecture on locally irregular decompositions.

Conjecture 3.3 ([17]

). For every decomposable graph G, we have χ irr (G) ≤ 3. Conjecture 3.3 is of course quite reminiscent of the 1-2-3 Conjecture, and, again, it might seem daring suspecting that such a statement holds for almost all graphs, regardless of their structure. Still, by the time we stated it, we were not able to spot any obvious counterexample to it, and we actually provided some support to it, which is recalled below. Before that, let us mention that Conjecture 3.3, if true, would be best possible, as attested, for instance, by cycles of length congruent to 2 modulo 4 (for the same reason why Observation 3.1 holds). Actually, there even exist infinitely many trees with irregular chromatic index 3, according to a result obtained with Baudon and Sopena [START_REF] Baudon | On the complexity of determining the irregular chromatic index of a graph[END_REF], which shows a difference with the 1-2-3 Conjecture, recall Theorem 2.8. Deciding if a decomposable graph G has irregular chromatic index at most 2 is in fact NP-complete [START_REF] Ahadi | Algorithmic complexity of proper labeling problems[END_REF][START_REF] Baudon | On the complexity of determining the irregular chromatic index of a graph[END_REF], while this is polynomial-time solvable for trees [START_REF] Baudon | On the complexity of determining the irregular chromatic index of a graph[END_REF].

In our seminal work [START_REF] Baudon | On decomposing regular graphs into locally irregular subgraphs[END_REF] on the subject, we verified Conjecture 3.3 for decomposable trees, complete graphs, complete bipartite graphs, some Cartesian products of graphs, and regular graphs with degree at least 10 7 .

Bounds on the irregular chromatic index

In this section are given series of bounds on the irregular chromatic index of particular classes of graphs, as steps towards Conjecture 3.3. The first bounds, which feature a general constant upper bound for all decomposable graphs, were exhibited jointly with Merker and Thomassen in [START_REF] Bensmail | Decomposing graphs into a constant number of locally irregular subgraphs[END_REF]. The other bounds, which hold for more specific classes of graphs (degenerate graphs), were obtained jointly with Dross and Nisse in [START_REF] Bensmail | Decomposing degenerate graphs into locally irregular subgraphs[END_REF].

General graphs

Towards Conjecture 3.3, the main bound we have established on the irregular chromatic index of decomposable graphs is the following: Theorem 3.4. For every decomposable graph G, we have χ irr (G) ≤ 328.

The most remarkable point behind Theorem 3.4 is that not only the established bound is constant, but also the proof behind it is based on a combination of rather elementary arguments. These arguments rely on the very particular structure of connected exceptions, and on the fact that, under particular assumptions, graphs can be decomposed into very particular auxiliary structures with low irregular chromatic index. We give a summary of our proof of Theorem 3.4 in what follows, giving a particular focus on the most general arguments that will for sure be reused in future bound improvements.

Ingredient 1: Reducing Conjecture 3.3 to connected graphs with even size

The very first ingredient behind the proof of Theorem 3.4 is a reduction of Conjecture 3.3 to connected graphs of even size. This is a very crucial point, as, as can be noted from Observation 3.31, all connected exceptions are of odd size, which makes many approaches risky. Suppose for instance that we are trying to decompose a graph G into locally irregular subgraphs. One very natural way of proceeding could be to first repeatedly extract locally irregular subgraphs G 1 , G 2 , . . . from G, and eventually wonder later how to combine these G i 's together to ensure the decomposition has a small number of parts. This last point is actually not the most troublesome. A more annoying one is rather: How can we be sure that, after extracting some locally irregular subgraphs G 1 . . . . , G i from G, what remains of G is still decomposable?

A simple solution to this issue arises from the very peculiar property of connected exceptions that they are all of odd size. In particular, if at some point we are dealing with a connected graph of even size, then for sure it is decomposable. This simple observation has a more general consequence, which is that, assuming we are dealing with a connected graph G with even size, we no longer have to struggle with the problem of exceptions as long as we extract from G connected subgraphs of even size so that, in what remains of G, all connected components also have even size. There is a remaining question, however, namely: What about connected decomposable graphs with odd size? From these graphs, it turns out that we can extract a locally irregular graph whose removal leaves connected components of even size only, thus a more favourable situation. More precisely: Theorem 3.5. If G is a connected decomposable graph with odd size, then G contains a locally irregular subgraph H such that every connected component of G -E(H) has even size.

A remarkable fact in the proof of Theorem 3.5 we gave (which is based, roughly, on studying cut-edges) is that, in general, we can find such an H with a very restricted structure. More precisely, we proved that the result still holds if one requires H to be a claw (K 1,3 ) or a claw with one edge subdivided once. As mentioned earlier, this simple yet useful result implies that Conjecture 3.3 can be reduced to connected graphs with even size, the price for this being a small additive term in the statement. Ingredient 2: Decomposing connected bipartite graphs with even size

The next ingredient in our proof of Theorem 3.4 is a strategy for decomposing connected bipartite graphs with even size into a few locally irregular subgraphs. More precisely, our main result here is the following: Theorem 3.7. If G is a connected bipartite graph with even size, then χ irr (G) ≤ 9.

Through Corollary 3.6, note that Theorem 3.7 shows that the irregular chromatic index of a decomposable bipartite graph is at most 10, which stands as a first result towards Conjecture 3.3 for bipartite graphs.

Our strategy for proving Theorem 3.7 is rather elementary. It is based on the fact that if all vertices in one partition class of G have even degree while the vertices in the other partition class have odd degree, then G is locally irregular. Let us call such a G an even-odd bipartite graph. The main idea of the proof is to remove some well-behaved subgraphs (i.e., with low irregular chromatic index) from G to obtain a graph which is very close to be even-odd. These subgraphs can in particular be obtained through the following well-known result: Lemma 3.8 (Folklore). Let G be a connected graph, and S be a set of vertices of G. If |S| is even, then there exists a collection of |S|/2 edge-disjoint paths in G such that every vertex in S is an end-vertex of precisely one of them, and the union of these paths forms a forest.

By looking closely at the proof of Lemma 3.8, it can be noted that, in the particular case where G is bipartite and S is a subset of one of the partition classes, the resulting mentioned forest actually has a very convenient property, which is that it admits a bipartition such that all vertices in one of the partition classes have even degree. We call such a forest a balanced forest. Another convenient aspect of balanced forests is that they have low irregular chromatic index. Indeed, since all trees of a balanced forest F necessarily have even size, and thus cannot be exceptions (odd-length paths in the present situation), we have χ irr (F) ≤ 3 (by a result from [START_REF] Baudon | On decomposing regular graphs into locally irregular subgraphs[END_REF]). Something stronger is actually true: Lemma 3.9. For every balanced forest F, we have χ irr (F) ≤ 2. Now, given a connected bipartite graph G with even size, we can already get quite close to an even-odd bipartite graph by extracting two balanced forests from G. That is: Corollary 3.10. If G is a connected bipartite graph of even size with partition classes A and B, then there exists, in G, a balanced forest F with leaves in A such that in G -E(F) all vertices in A have even degree. Corollary 3.11. Let G be a connected bipartite graph with partition classes A and B, and let v be a vertex in B. If all vertices in A have even degree, then there exists, in G, a balanced forest F with leaves in B such that in G -E(F) all vertices in B \ {v} have odd degree.

In other words, given a connected bipartite graph G with even size and partition classes A and B, we can extract two balanced forests from G so that G becomes even-odd except maybe because of one vertex v which does not have the desired degree parity. In that case, we continue as follows. Assume the vertices in A have even degree while the vertices in B \ {v} have odd degree. Recall that all the way made up to this point was to try to make G locally irregular. Thus, if v has even degree but none of its neighbours has the same degree, then we are done. So we can assume that there is a u ∈ A such that uv is an edge and d(u) = d(v). Let us here remove uv from G. Now v has odd degree in the remaining graph Guv, while u has even degree. If Guv is not locally irregular, then, this time, this must be because v is adjacent to a vertex u ∈ B with u u and d(v) = d(u ). Again, we get rid of this degree conflict by removing vu from Guv. Repeating these arguments over and over, because the degrees of the successive faulty vertices keep on decreasing, we end up with the following: Lemma 3.12. Let G be a bipartite graph with partition classes A and B, and v be a vertex of B. If all vertices in A have even degree and all vertices in B \ {v} have odd degree, then there exists, in G, a (possibly empty) path P starting in v such that G -E(P ) is locally irregular.

Regarding D, Theorem 3.15 implies that it can be further decomposed into log 2 (2 • 10 10 + 3) + 1 bipartite graphs in which all connected components have even size, each of which decomposes into at most nine locally irregular subgraphs by Theorem 3.7. Together with the decomposition of H into at most three locally irregular subgraphs, this results in a decomposition of G into at most 327 locally irregular subgraphs.

Degenerate graphs

The proof of Theorem 3.4 presented in the previous section mainly relies on decompositions of connected degenerate graphs with even size into a logarithmic (in the degeneracy) number of bipartite graphs of even size. A downside of this method is that we do not know yet whether connected bipartite graphs with even size, in general, verify Conjecture 3.3, as, at this point, the best result of this sort we have is Theorem 3.7. More precisely, combining these results yields the following: Corollary 3.18. For every connected k-degenerate graph G with even size, we have

χ irr (G) ≤ 9 • ( log 2 (k + 1) + 1).
Consequently, by Corollary 3.6, for every decomposable k-degenerate graph G, we have

χ irr (G) ≤ 9 • ( log 2 (k + 1) + 1) + 1.
Towards improving the bound in Theorem 3.4, at least for some graph classes, it seems natural wondering about decompositions of connected degenerate graphs into bipartite graphs for which Conjecture 3.3 holds. Exploiting this approach, we came up with the following: Theorem 3.19. For every connected k-degenerate graph G with even size, we have χ irr (G) ≤ 3k. Consequently, by Corollary 3.6, for every decomposable k-degenerate graph G, we have χ irr (G) ≤ 3k + 1. Theorem 3.19 improves Corollary 3.18 for graphs with low degeneracy. More precisely, 3k < 9 • log 2 (k + 1) + 1 whenever k ≤ 17. As notable cases, we get that decomposable 2degenerate graphs (which include outerplanar graphs, series-parallel graphs, etc.) have irregular chromatic index at most 7, and decomposable planar graphs, which are 5-degenerate, have irregular chromatic index at most 16. This is particularly interesting when reminding that exceptions are of degeneracy at most 2, since this means that graphs with low degeneracy are tricky graphs when dealing with Conjecture 3.3. The rest of this section is dedicated to giving some clues about our proof of Theorem 3.19. The idea here is to decompose connected degenerate graphs of even size into some decomposable bipartite cacti. Recall that a cactus is a graph in which no two cycles intersect in more than one vertex. Note that all exceptions having cycles have odd-length cycles only; this means that a connected bipartite cactus is decomposable as soon as it has at least one cycle. The other way around, a bipartite cactus is not decomposable as soon as it has a connected component being an odd-length path. We then say that a cactus is good if it is bipartite and none of its connected components is an odd-length path.

A first important point is that good cacti verify Conjecture 3.3. That is, towards improving Corollary 3.18, it is worth decomposing a graph into good cacti. Theorem 3.20. For every good cactus G, we have χ irr (G) ≤ 3.

The proof of Theorem 3.20 is straightforward, and does not require particularly elaborate arguments. It might be assumed that G is connected. If G is a tree (different from an odd-length path), then the result follows from [START_REF] Baudon | On decomposing regular graphs into locally irregular subgraphs[END_REF]. Otherwise, G has cycles, in which case we look for an "end-cycle", which turns out to be a very appropriate place to invoke inductive arguments.

The second step in the proof of Theorem 3.19 is proving that connected k-degenerate graphs with even size do decompose into k good cacti, so that the full result then follows from Theorem 3.20. This is something that follows mainly from the following lemma, which, roughly • Weak distinction: two adjacent vertices u and v of G are considered distinguished if there is an α ∈ {1, . . . , } such that σ α (u) σ α (v).

• Standard distinction: two adjacent vertices u and v of G are considered distinguished if, assuming ω(uv) = (α, β), we have σ α (u) σ α (v).

• Strong distinction: two adjacent vertices u and v of G are considered distinguished if, for every α ∈ {1, . . . , }, we have

σ α (u) = σ α (v) = 0, or σ α (u) σ α (v).
Assuming ω verifies one of the weak, standard and strong distinction conditions for every pair of adjacent vertices, we say that ω is a weak, standard or strong ( , k)-colouring, respectively, and that G is weakly, standardly or strongly ( , k)-coloured, respectively. We also say that G is weakly, standardly or strongly ( , k)-colourable, respectively, if there are , k ≥ 1 with ≤ and k ≤ k such that G can be weakly, standardly or strongly ( , k )-coloured, respectively. These concepts are illustrated in Figure 3.4.

The next sections are organised as follows. As already mentioned, the notions of weak, standard and strong ( , k)-colourings can be employed to generalise neighbour-sum-distinguishing edge-weightings and locally irregular edge-colourings. In Section 3.3.1, we explore these connections. In particular, we recall known results and translate them into our new terminology.

Playing with the parameters and k and the three distinction conditions above, we also come up with new problems, some of which we believe are of independent interest. In particular, we wonder whether almost all graphs can be weakly, standardly, or even strongly (2, 2)-coloured. If true, then this would imply side decomposition results related to the 1-2-3 Conjecture. The strong, standard and weak versions of that question are formally discussed in Section 3.3.2.

( , k)-colourings and results from the literature

As a warm up, we start, in this section, by making first observations and remarks on weak, standard and strong colourings. We then survey some of the results from literature that are directly connected to these notions. More precisely, we explain which notions in the literature are encompassed by weak, standard and strong colourings, and, by rephrasing known results under that new terminology, we derive first results.

Early observations

First of all, we note that, according to the definitions, every result holding for some version of ( , k)-colourings also holds for the weaker versions. This is why, in Section 3.3.2, we start by considering strong colourings, then standard colourings, and, finally, weak colourings. Observation 3.22. A strong ( , k)-colouring is also a standard ( , k)-colouring. Analogously, a standard ( , k)-colouring is also a weak ( , k)-colouring.

Observe that the converse direction is not true in general, i.e., that a given distinguishing ( , k)-colouring does not necessarily fulfil stronger distinction conditions. A good illustration is the fact that K 3 can be weakly (2, 2)-coloured but not standardly (2, 2)-coloured. There are situations, however, where the three variants behave similarly. We state some such below.

First of all, we recall that, for some values of and k, some distinguishing ( , k)-colourings are equivalent to other kinds of distinguishing colourings and weightings. Most of these observations are straightforward; in particular, it can easily be checked that some of these results do not hold for others of our colouring variants. For weak colourings, it can be observed that a related notion of the literature is that of neighbour-multiset-distinguishing edge-weightings. Observation 3.25. Weak (k, 1)-colourings and neighbour-multiset-distinguishing k-edge-weightings are equivalent notions.

In Observation 3.23, we noticed that, for (1, k)-colourings, all three distinction conditions are equivalent. In the following result, we point out another context where the three colouring variants coincide. An implication of this observation is to be stated later below. Observation 3.26. In regular graphs, weak, standard and strong (2, 1)-colourings are equivalent notions.

Encompassing results from literature

As mentioned earlier, particular (1, k)-colourings or ( , 1)-colourings correspond to some distinguishing edge-weighting notions. Thus, every conjecture or result related to one of these edge-weighting notions translates into our formalism. We inspect this aspect in what follows.

We start off with neighbour-sum-distinguishing edge-weightings. Recall that, according to Observation 3.23, being strongly (1, k)-colourable is equivalent to being neighbour-sumdistinguishing k-edge-weightable. Thus, all general constant upper bounds and results (such as those mentioned in Section 2.1) on the parameter χ e σ yield results on strong colourability (hence on the weaker variants as well, recall Observation 3.22). Here, recall that the leading conjecture is the 1-2-3 Conjecture, which translates into the following: Conjecture 3.27. Every nice graph is strongly (1, 3)-colourable.

The best result to date towards the 1-2-3 Conjecture is Theorem 2.11, which here says that every nice graph is strongly (1, 5)-colourable. Recall that, according to Theorem 2.4, determining the value of χ e σ (G) for a given graph G is NP-complete, and that this remains true for regular (cubic) graphs (Theorem 2.16). This result is of prime interest, as all distinguishing weighing and colouring notions considered in this section tend to be equivalent when 1) only two weights or colours are considered, and 2) the graph is regular (recall Observation 3.26). Thus, Theorem 2.16, by itself, directly establishes the general hardness of finding weak, standard and strong colourings. Now consider locally irregular edge-colourings. By Observation 3.24, we get that locally irregular k-edge-colourings are precisely standard (k, 1)-colourings. Recall that the guiding line regarding locally irregular edge-colourings is Conjecture 3.3, which here translates into: Conjecture 3.28. Every decomposable graph is standardly (3, 1)-colourable.

In particular, Theorem 3.4, the best result to date here, is equivalent to stating that every decomposable graph is standardly (328, 1)-colourable.

Finally consider neighbour-multiset-distinguishing edge-weightings. The leading conjecture here is the straight multiset weakening of the 1-2-3 Conjecture, Conjecture 2.12, which here translates into the following: Conjecture 3.29. Every nice graph is weakly (3, 1)-colourable.

Recall that the best result towards Conjecture 3.29 was proved in [START_REF] Addario-Berry | Vertex colouring edge partitions[END_REF], where it was proved that all nice graphs admit neighbour-multiset-distinguishing 4-edge-weightings. Hence all nice graphs are weakly (4, 1)-colourable.

A new general problem

As seen in Section 3.3.1, some of the (1, k)-colouring and ( , 1)-colouring variants correspond to distinguishing weighting and colouring notions already considered in literature. In particular, for such values of and k, there is still some gap between the corresponding conjectures and the best results we know to date. One way to get some sort of side progress, could be to prove the existence of ( , k)-colourings (for some distinction condition) where none of and k is 1, and + k or max{ , k} is as small as possible.

In particular, the main problem we consider in the rest of this section, which corresponds to minimising max{ , k}, and to which we could not find any obvious counterexample, reads as follows. By a nicer graph, we mean a graph with no connected component being K 2 or K 3 .

Conjecture 3.30. Every nicer graph is strongly (2, 2)-colourable.

The main reason for suspecting that K 2 and K 3 might be the only connected graphs admitting no strong (2, 2)-colourings is that they are the only connected exceptional graphs (recall Theorem 3.2) admitting no neighbour-sum-distinguishing 2-edge-weighting. This can be proved easily by considering each of the three types of exceptions separately. In what follows, we list evidence we got towards Conjecture 3.30. We do it gradually, by first considering Conjecture 3.30 in its literal stronger form. We then consider its standard weakening, before finally considering its weak weakening.

Strong Conjecture

We first consider Conjecture 3.30 in its literal form, namely: Conjecture 3.32 (Strong Conjecture). Every nicer graph is strongly (2, 2)-colourable.

Using arguments that are standard in this context, we verified the Strong Conjecture for nicer complete graphs and nicer bipartite graphs. The proof for complete graphs is by developing an adequate inductive scheme, that is reminiscent of the proof of Theorem 2.5. In order to prove the result for bipartite graphs, the key idea is to focus on odd multi-cacti, since all other bipartite graphs G verify χ e σ (G) ≤ 2 and are thus strongly (1, 2)-colourable. For an odd multi-cactus, the Strong Conjecture can be proved by exploiting the degenerate structure.

Standard Conjecture

We here consider the standard weakening of Conjecture 3.30: Conjecture 3.33 (Standard Conjecture). Every nicer graph is standardly (2, 2)-colourable.

Note that a standard ( , k)-colouring is nothing but a decomposition into graphs admitting neighbour-sum-distinguishing k-edge-weightings. From that perspective, it could be interesting to wonder whether graphs, in general, decompose into a constant number of graphs verifying the 1-2-3 Conjecture. Of course, the 1-2-3 Conjecture, if true, would imply that every nice graph decomposes into one graph verifying the 1-2-3 Conjecture. We however believe this is an interesting aspect to consider now, as, to date, there are not that many graphs that are known to verify the 1-2-3 Conjecture.

Towards the Standard Conjecture, we thus also raise the following related conjecture, which is, in a sense, a weakening of the 1-2-3 Conjecture: Conjecture 3.34. Every nice graph is standardly (2, 3)-colourable. That is, every nice graph decomposes into at most two graphs verifying the 1-2-3 Conjecture.

Our first result towards the Standard Conjecture is that all nice graphs admit standard (40, 3)-colourings, which can be proved similarly as Theorem 3.4. We also verified the conjecture for nice subcubic graphs and nice 2-degenerate graphs, by exploiting their low degeneracy.

We also verified Conjecture 3.34 for nice 9-colourable graphs. The proof of this is by showing that every nice 9-colourable graph G can be decomposed into two nice 3-colourable graphs G R and G B . Since nice 3-colourable graphs verify the 1-2-3 Conjecture (recall Theorems 2.6 and 2.9), we have both χ e σ (G R ) ≤ 3 and χ e σ (G B ) ≤ 3, and the result follows. The only tricky part is that, when decomposing G into G R and G B , one should be careful that none of G R and G B includes K 2 as a connected component. In case one of G R and G B includes such a K 2 , we proved that we can switch edges between these two graphs to get rid of it, so that the general desired properties are preserved. We state the full statement, as we think it is of independent interest. The proofs of these two results are quite similar, as they are based on modifications of the proof of Theorem 2.11. In their result, Kalkowski, Karoński and Pfender proved that every nice graph admits a neighbour-sum-distinguishing {1, 2, 3, 4, 5}-edge-weighing. By looking carefully at how the proof works, it can actually be generalised to more sets of five weights. Theorems 3.37 and 3.38 are proved by starting from an initial neighbour-sum-distinguishing edge-weighting assigning a particular set of five weights, and modifying these weights by altering their value in some fashion and assigning a particular colour to them. More precisely:

• To prove Theorem 3.37, we start from a neighbour-sum-distinguishing {-2, -1, 0, 1, 2}edge-weighting. We colour red every edge with weight in {1, 2}. We colour blue every edge with weight in {-2, -1} and multiply its weight by -1. We colour green every edge with weight 0 and change its weight to 1. This is illustrated in Figure 3.5.

• To prove Theorem 3.38, we start from a neighbour-sum-distinguishing {1, 2, 3, 4, 6}-edgeweighting. We colour red every edge with weight in {1, 3}. We colour blue every edge with weight in {2, 4, 6} and halve its weight.

In both cases, it can be checked that, by how the weights are modified and coloured, for every edge its two ends remain distinguishable. Furthermore, the resulting sets of coloured weights are the desired ones in both cases.

Conclusion and perspectives

Summary of the contributions in the chapter

In this chapter, we have presented progresses towards understanding locally irregular decompositions, and in particular towards understanding Conjecture 3.3, which we raised during my Ph.D. studies. An important result that was missing here, was an evidence that indeed there is an absolute constant bounding χ irr (G) for all decomposable graphs G. This is what Theorem 3.4 establishes. As mentioned earlier, a remarkable fact lies in the proof of that result, which is based on a combination of rather elementary lemmas. An important point to mention also is that the general approach we have designed can be subject to improvements. In particular, several of our elementary lemmas are not optimal, and improving any of them would lead to an improvement of our bound, in general or for particular graph classes. This thought is supported by Theorem 3.19, which improves on Theorem 3.4 for degenerate graphs.

Another contribution in this chapter is the theory developed in Section 3.3, for which the aim was to understand better the connection between locally irregular decompositions and the 1-2-3 Conjecture. Although the resulting presented framework relies on even more artificial notions, a satisfying thing is that it succeeds in encapsulating many results and notions from the field, at least those around the 1-2-3 Conjecture. A nice thing also is the related conjectures, Conjecture 3.30, its weakenings, and Conjecture 3.34, we ran into during our investigations.

Recent results and developments

Over the last years, a number of new results towards Conjecture 3.3 were obtained in parallel, some of which improve results presented in this chapter. The most important series of progresses is due to Lužar, Przybyło and Soták in [65]. Their main result is an improvement of the upper bound in Theorem 3.7, from 9 to 6. Following then our proof scheme, this result improves several others of ours; in particular, this led them to improving the bound in Theorem 3.4 from 328 to 220. Their improved result on decomposable bipartite graphs relies on the use of vertex-parity edge-colourings, which are edge-colourings where, for a graph G, and given a function π : V (G) → {0, 1}, the number of incident edges with any given colour incident to any vertex v is congruent to π(v) modulo 2. Note that a such tool indeed fits well in this context, as it is sort of related to the notion of even-odd bipartite graph used in Section 3.2.1. Some results were also obtained towards Conjecture 3.3 for decomposable graphs with bounded maximum degree. In [START_REF] Baudon | On locally irregular decompositions of subcubic graphs[END_REF], we observed with Baudon, Hocquard, Senhaji and Sopena that decomposable graphs G with maximum degree ∆ verify χ irr (G) ≤ 3∆ -2. This can be proved through Corollary 3.6, and by repeatedly extracting paths of length 2 from graphs of even size with leaving all resulting connected components of even size. For decomposable graphs G with maximum degree at most 3, which is a tricky class of graphs to consider as it includes all exceptional graphs, we proved that χ irr (G) ≤ 5 holds through an induction scheme. Refined arguments led Lužar, Przybyło and Soták to improve this bound down to 4 in [65].

I am also aware of results in [START_REF] Lintzmayer | Decomposing split graphs into locally irregular graphs[END_REF] regarding split graphs and Conjecture 3.3. In that work, Lintzmayer, Mota and Sambinelli not only proved the conjecture for decomposable split graphs, but also gave a good characterisation of split graphs with irregular chromatic index 2. This result is mainly by studying carefully the ways of decomposing complete graphs into graphs that are close to locally irregular.

Several results also appeared in literature regarding the variants of Conjecture 3.30. First off, as mentioned in the concluding section of Chapter 2, Vučković provided in [START_REF] Vučković | Multi-set neighbor distinguishing 3-edge coloring[END_REF] a proof of the multiset version of the 1-2-3 Conjecture (Conjecture 2.12), which in the current chapter is Conjecture 3.29. This result directly improves our Theorem 3.37, due to Observation 3.25.

New results on Conjecture 3.30 were also obtained by Przybyło, mainly through the use of the probabilistic method. He proved in [START_REF] Przybyło | A note on the weak (2, 2)-Conjecture[END_REF] that the Weak Conjecture holds for graphs with minimum degree at least 3660. In [START_REF]On the Standard (2, 2)-Conjecture[END_REF], he proved the Standard Conjecture for graphs with minimum degree at least 10 6 .

Perspectives for future work

A first natural direction for research would be to improve all upper bounds we have towards Conjecture 3.3 that do not quite meet the conjectured bound. The most interesting direction in that line would be to improve the currently best-known bound towards Conjecture 3.3, which is 220 (proved in [65]). One way to achieve this could be by improving some of the ingredients in our proof scheme of Theorem 3.4. In particular, by proving that connected bipartite graphs with even size verify Conjecture 3.3, the exact same proof would yield that every decomposable graph has irregular chromatic index at most 76. Another possible source of improvement would be to improve Przybyło's Theorem 3.17 to graphs with smaller minimum degree.

It would also be nice understanding Conjecture 3.3 for more classes of graphs. In particular, we have noticed during several occasions that Conjecture 3.3 and the 1-2-3 Conjecture are sort of related. As seen in previous Chapter 2, bipartite graphs are among the most understood graphs in the context of the 1-2-3 Conjecture. From these thoughts, it is intriguing that bipartite graphs seem so troublesome regarding Conjecture 3.3. It thus seems that understanding Conjecture 3.3 for bipartite graphs would not only be a great step towards getting better upper bounds, but also towards understanding better locally irregular decompositions in general.

Still about bipartite graphs, it would also be nice establishing some sort of counterpart to Theorem 2.10 for locally irregular decompositions. That is, it is a legitimate question asking whether there is a good characterisation of decomposable bipartite graphs G with χ irr (G) ≤ 2. It can be checked that, in this context as well, odd multi-cacti form a class of graphs to keep in mind. But the situation is actually a bit more complicated here than it is for neighboursum-distinguishing 2-edge-weightings. In particular, let us recall that infinitely many trees have irregular chromatic index 3 (according to [START_REF] Baudon | On the complexity of determining the irregular chromatic index of a graph[END_REF]). Also, for establishing Theorem 2.10 a key result was Observation 2.7, which, at the moment, has no equivalent for locally irregular decompositions of bipartite graphs. Other such key results include the fact that a bipartite graph G verifies χ e σ (G) ≤ 2 as soon as δ(G) ≥ 3 [START_REF] Thomassen | The 3-flow conjecture, factors modulo k, and the 1-2-3-conjecture[END_REF] or G is 3-connected [START_REF] Lu | Vertex-coloring 2-edge-weighting of graphs[END_REF] -results that, again, have no analogues here. Thus, many more steps need to be made towards understanding all this. Let us mention, however, that there are partial results. In particular, with Merker and Thomassen, we proved in [START_REF] Bensmail | Decomposing graphs into a constant number of locally irregular subgraphs[END_REF] that every 16-edge-connected bipartite graph has irregular chromatic index at most 2. This was established through some of the many nice factor results established by Thomassen, such as Lemma 2.25, which are very promising tools in this context.

More generally, towards Conjecture 3.3 we would highly benefit from the understanding of simple graph classes that include all exceptional graphs. Indeed, one reason why our upper bounds are always a bit off is the reduction of the conjecture to graphs of even size, established Chapter 4

Personal conclusion and perspectives

This document was an opportunity for me to summarise some of the research I have been conducting towards understanding the fascinating field of distinguishing labellings, and more precisely several aspects of the 1-2-3 Conjecture. From my point of view, the obtained results are actually not the most interesting thing. What is more interesting is the connections we managed to establish between some aspects of the conjecture and other notions of graph theory. I also did my best to show how various and numerous the tools and arguments we use in this context can be. Something interesting also is that the questions we have investigated here are very easy to catch. Most of the whole field is actually very easy to get into, even for people not familiar with it. All these reasons explain why I think this field has so much to offer.

A lot of aspects and open questions, such as the ones mentioned in the concluding sections of Chapters 2 and 3, remain open in the field and will for sure occupy some of my research in the near future. Some of these will actually be part of Foivos Fioravantes' Ph.D. thesis, which I am currently co-supervising with Nicolas Nisse since October 2019. I am pretty sure nice progresses will result from this. Certainly some other aspects, not mentioned in the current document, will pop out at some point, because, as I hopefully managed to make it apparent, distinguishing labellings form a field full of nice possibilities to anyone curious enough for not focusing on the main hard questions only. I can definitely see lots of possibilities here.

To be a bit more precise, among the directions I have mentioned, the following ones seem like the most promising to me, and I hope to get some progress there in the next years. The most important step would be to prove the 1-2-3 Conjecture, or at least to improve Theorem 2.11, and, to that aim, as I said earlier I am pretty confident that algebraic tools are the key. I am thus willing to take part to the development of algebraic tools dedicated to neighbour-sumdistinguishing edge-weightings. Regardless of our success here, I think it would be interesting to keep on improving Kalkowski's Algorithm (Theorem 2.14), as we did in Theorem 2.18, because this is the kind of brilliant results that, once fully understood, can lead to more consequences. I would also like to study further the connection between the 1-2-3 Conjecture and other classical notions of graph theory, in particular proper vertex-colourings, and investigate variants of the 1-2-3 Conjecture, for instance by pursuing the "quest" towards a challenging directed variant or investigating e.g. the product version and equitable version. Regarding locally irregular decompositions, our results in Section 3.2 show that progresses towards Conjecture 3.3 can be obtained through combining elementary tools, which, when we stated the conjecture, was not something we have imagined. So, I am pretty sure that trying to push bounds further down towards Conjecture 3.3 is an interesting direction for research, as it mainly requires being innovative and coming up with good decomposition strategies. For these reasons I would definitely like to put more efforts into this in the near future.

As a more general perspective, I hope to continue contributing to more and more problems of graph theory. My latest interests include extending the classical colouring theory to decorated graphs, and metric problems in graphs, such as problems inspired from the notion of metric dimension of graphs. In the near future, I hope to continue to work on these topics, and that this will be done through more fruitful collaborations. I also plan on improving my general understanding of algorithmic theory, which is a very attractive field.

Figure 1 . 1 :

 11 Figure 1.1: Examples of the two main types of objects studied in this document: a neighboursum-distinguishing edge-weighting (a), and a locally irregular decomposition (b).

Figure 2 . 1 :

 21 Figure 2.1: A graph G that is regular, thus not locally irregular (a). For an edge-weighting ω of G in which no two adjacent vertices are incident to the same sum of weights (b), by replacing each edge e by ω(e) parallel edges we get a locally irregular multigraph G with the same adjacencies as G (c).

Theorem 2 . 22 .

 222 Let a, b ∈ Z be odd integers with b = a + 2. A 2-connected bipartite graph G does not have the {a, b}-property if and only if G is an odd multi-cactus.

Lemma 2 . 24 .

 224 Let G be a connected bipartite graph, and let a, b ∈ Z be odd integers with b = a + 2.

Figure 2 . 4 :

 24 Figure 2.4: Constructing graphs without the {-1, 1}-property.

Theorem 2 .

 2 31 ([20]). For every digraph D, we have χ +,+ (D) ≤ 3.Proof. The crucial point is that, when weighting an arc --→ uv of D, this affects σ + (u) while this does not affect σ + (v). This permits to prove the claim by induction on |V (D)| + |A(D)| in a very straight way. Let v be a vertex of D with d + (v) ≥ d -(v); such a vertex exists since u∈V (D) d -(u) = u∈V (D) d + (u). Now consider D the digraph obtained from D by removing all arcs outgoing from v.

Conjecture 2 . 32 .

 232 For every nice digraph D, we have χ +,-(D) ≤ 3.

Figure 2 . 5 :

 25 Figure 2.5: Illustration of the arguments why some orientation of the square of C 7 admits no (+, -)-distinguishing 2-arc-weighting. Having----→v 2 v 1 weighted 1 (a) forces two adjacent arcs to be weighted differently (b). By then repeatedly considering a weighted arc ---→ v i v j such that the second arc outgoing from v i is weighted while the second arc incoming to v j is not, or vice versa, we deduce that another arc adjacent to ---→ v i v j has its weight forced so that σ + (v i ) σ -(v j ) ((c) to (g)). The deduction process here ends up with σ + (v 6 ) = σ -(v 4 ) regardless of the weight of ----→ v 6 v 4 , a contradiction.

Figure 2 . 6 :

 26 Figure 2.6: A digraph D (a) and its associated bipartite graph B(D) (b). Because D is nice, B(D) is also nice. According to the arguments in the proof of Theorem 2.33, we have χ +,-(D) = χ e σ (B(D)). Since B(D) is C 14 , we have χ +,-(D) = χ e σ (B(D)) = 3 by Theorem 2.10.

  with χ +,-(D) = 3: if B(D) is a bipartite graph with χ e σ (B(D)) = 3, then χ +,-(D) = 3. For instance, the digraph D from Figure 2.5 we mentioned earlier verifies χ +,-(D) = 3, which can be explained because B(D) is C 14 (see Figure 2.6), which verifies χ e σ (C 14 ) = 3, recall Theorem 2.10. We can actually state something a bit stronger because of Theorems 2.10 and 2.33: Corollary 2.34. A nice digraph D has χ +,-(D) = 3 if and only if B(D) is an odd multi-cactus.

Theorem 2 .

 2 35 ([58]). For every nice digraph D, we have χ -,+ (D) ≤ 4. Horňák, Przybyło and Woźniak did not find a digraph showing the tightness of Theorem 2.35; they thus left the following conjecture, reminiscent of the 1-2-3 Conjecture, open: Conjecture 2.36 ([58]). For every nice digraph D, we have χ -,+ (D) ≤ 3.

  .2 for an example of a locally irregular decomposition of a graph.

Figure 3 . 1 :Figure 3 . 2 :

 3132 Figure 3.1: Graphs that are or are not locally irregular. Red edges are edges whose two ends have the same degree. Green edges are edges whose two ends have different degrees. Graphs (a) and (b) are not locally irregular due to red edges, while (c) is.

Corollary 3 . 6 .

 36 Let G be a hereditary family of graphs. Then, we have max χ irr (G) : G ∈ G is decomposable ≤ max χ irr (G) : G ∈ G has even size + 1.

Figure 3 . 4 :

 34 Figure 3.4: Three (2, 2)-colourings of K 4 with colours red and green. It can be checked that (a) shows a weak colouring, which is not a standard colouring because vertices c and d are joined by a red edge but their incident red sum equals 3. It can be checked that (b) shows a standard colouring, which is not a strong colouring because vertices a and c both have incident red sum 2. It can be checked that (c) shows a strong colouring.

Observation 3 . 23 .

 323 Weak, standard and strong (1, k)-colourings and neighbour-sum-distinguishing k-edge-weightings are equivalent notions. Observation 3.24. Standard (k, 1)-colourings and locally irregular k-edge-colourings are equivalent notions.

Observation 3 . 31 .

 331 Every connected exception different from K 2 and K 3 verifies Conjecture 3.30.

Lemma 3 . 35 .

 335 Assume that a nice graph G can be 2-edge-coloured with red and blue so that the induced red subgraph G R and the blue subgraphG B satisfy χ(G R ) = r and χ(G B ) = b with r, b ≥ 2. Then G can be 2-edge-coloured in such a way that χ(G R ) ≤ r, χ(G B ) ≤ b, and G R and G B are nice.We also verified Conjecture 3.34 for d-regular graphs with d {10, 11, 12, 13, 15, 17}. The proof is a combination of the ideas in the proof of Theorem 2.18 and probabilistic arguments.Weak ConjectureFinally, the weaker form of Conjecture 3.30 reads as follows: Conjecture 3.36 (Weak Conjecture). Every nice graph is weakly (2, 2)-colourable. Towards the Weak Conjecture, we proved the following two results, which are very close: Theorem 3.37. Every nice graph G is weakly (3, 2)-colourable. Theorem 3.38. Every nice graph G is weakly (2, 3)-colourable.

Figure 3 . 5 :

 35 Figure 3.5: Illustration of the proof of Theorem 3.37. Given a neighbour-sum-distinguishing {-2, -1, 0, 1, 2}-edge-weighting of a graph (a), we modify the weights and colour them so that a weak (3, 2)-colouring results (b).

  into three (non-empty) stable sets. Up to relabelling the V i 's, we can assume that |V 1 | and |V 2 | have the same parity, so that |V 1 | + |V 2 | is even.

Throughout this document, when saying that a graph class F admits a good/easy/nice characterisation, we mean that the problem of deciding whether a given graph belongs to F can be solved in polynomial time.

There is actually an easier (but somewhat related) way to 2-edge-weight nice trees, which essentially consists in repeatedly extending a partial neighbour-sum-distinguishing 2-edge-weighting from any root towards the leaves.

If the path P we get that way is of even length, then it is decomposable into at most two locally irregular subgraphs and we managed to make G locally irregular for a cheap price. The last problem is when P has odd length, i.e., is an exception. In that case, the idea is, prior to extracting P , to first extract from G a cycle C going through v, if any. Note that extracting a cycle from G, though it can disconnect the graph, does not change the parity of the vertex degrees. If such a cycle C does not exist, then all edges incident to v are cut-edges, in which case different easy arguments, which we voluntarily omit, can be employed. If such a C does exist, then the idea is essentially to decompose C and P into locally irregular subgraphs together, which can be proved possible: Lemma 3.13. Let G be a bipartite graph, and v be a vertex of G. If G is the edge-disjoint union of an induced cycle C through v and a path P starting at v, then χ irr (G) ≤ 4. Lemma 3.13 might of course be not best possible according to Conjecture 3.3. However, proving the bound 4 here requires much less efforts than proving the bound 3 requires.

The proof of Theorem 3.7 is eventually obtained by combining all previous ideas. To summarise, the first step is to make G as close to even-odd as possible. That task can be achieved by extracting from G at most two balanced forests, which decompose into at most four locally irregular subgraphs. If the remaining of G is locally irregular, then we get a decomposition into at most five locally irregular subgraphs. Otherwise, i.e., the remaining of G is not locally irregular, we extract from G a path P and a cycle C (being both possibly empty) intersecting in the faulty vertex so that what remains of G is locally irregular. The union of P and C can further be decomposed into at most four locally irregular subgraphs. This yields, in total, a decomposition of G into at most nine locally irregular subgraphs.

Ingredient 3: Decomposing connected degenerate graphs with even size

The last ingredient in our proof of Theorem 3.4 is the fact that connected degenerate graphs with even size decompose into a limited number of connected bipartite graphs with even size. The main lemma we use to prove this reads as follows: Lemma 3.14. If G is a graph with a vertex v such that Gv is bipartite, then there exists a set E of at most d(v)/2 edges incident to v such that G -E is bipartite.

In particular through applications of Lemma 3.14, our main result is here the following: Theorem 3.15. Let d ≥ 1 be a natural number. If G is a d-degenerate graph in which every connected component has even size, then G can be decomposed into at most log 2 (d + 1) + 1 bipartite graphs in which all connected components have even size.

Final recipe: Using all ingredients together

We now have almost all ingredients in hand for describing our proof of Theorem 3.4. By Corollary 3.6, it is sufficient to prove that χ irr (G) ≤ 327 holds for every connected graph G with even size. The last tool we need is the following lemma, which can be proved by repeatedly putting aside vertices of large degree. Back to the proof of Theorem 3.4, by the previous lemma, G can be decomposed into two graphs D and H so that D is (2•10 10 +2)-degenerate, every connected component of D has even size, and the minimum degree of H is at least 10 10 . We now decompose D and H into locally irregular graphs independently. Regarding H, we make use of the following result of Przybyło, which was proved through a use of the probabilistic method: Theorem 3.17 ([66]). For every graph G with δ(G) ≥ 10 10 , we have χ irr (G) ≤ 3.

speaking, means that, given a graph, we can repeatedly add pairs of its adjacent edges to a partial decomposition into two good cacti until a decomposition of the whole graph results. Lemma 3.21. Let G be a graph, and let (T 1 , T 2 ) be a partial decomposition of G into two good cacti. Consider a vertex v of G belonging to none of T 1 , T 2 . Then, for every two edges vu, vw incident to v, there exists a partial decomposition

The proof of Lemma 3.21 roughly consists in studying T 1 and T 2 to check where these two edges should be added. A very important point here lies in the fact that we are adding edges in pairs. In particular, when adding the two edges to a single one of T 1 and T 2 , this implies we cannot create a connected component being an odd-length path (which, recall, is the only type of exception here), unless the original cactus already had one. Another important property here is that any connected bipartite cactus with maximum degree at least 3 cannot be an exception, and adding edges to it (with keeping it a good cactus, in particular without breaking bipartiteness) cannot make it become an exception.

In [START_REF] Bensmail | Decomposing degenerate graphs into locally irregular subgraphs[END_REF], we also improved the previous results for restricted classes of degenerate graphs. In particular, we proved that, for any k ≥ 2, every k-tree can be decomposed into k trees with irregular chromatic index at most 2, and thus into at most 2k locally irregular subgraphs. We also provided a better result for decomposable planar graphs. Since every planar graph is 5degenerate, Theorem 3.19 yields that every such decomposable graph has irregular chromatic index at most 16. We here decreased this bound slightly, down to 15. The proof of this is by showing that connected decomposable planar graphs with even size decompose into four good cacti (each of which decomposes into at most three locally irregular subgraphs, recall Theorem 3.20) and one forest whose all connected components have even size (which decomposes into at most two locally irregular subgraphs, according to [START_REF] Baudon | On the complexity of determining the irregular chromatic index of a graph[END_REF]). Proving this is mainly by taking advantage of local light structures.

Binding the 1-2-3 Conjecture and Conjecture 3.3

In this section, we introduce some notions and terminology with the general purpose of enclosing the 1-2-3 Conjecture and Conjecture 3.3 within a common context. Hence, the goal here is to better understand the intrinsic connection between neighbour-sum-distinguishing edge-weightings and locally irregular decompositions. In other words, we aim at comprehending better the very decompositional nature of the 1-2-3 Conjecture. This is a direction we have first considered jointly with Baudon, Davot, Hocquard, Przybyło, Senhaji, Sopena and Woźniak in [START_REF] Baudon | A general decomposition theory for the 1-2-3 Conjecture and locally irregular decompositions[END_REF], and pushed further later with Przybyło in [START_REF] Bensmail | Decomposability of graphs into subgraphs fulfilling the 1-2-3 Conjecture[END_REF].

The main ideas come from the observation that a locally irregular -edge-colouring of a graph G is, put differently, a decomposition of G into graphs G 1 , . . . , G verifying χ e σ (G 1 ) = 1, . . . , χ e σ (G ) = 1. Another way to see this, is that a locally irregular edge-colouring is an edgecolouring where each colour class yields a graph with small value of the parameter χ e σ . These observations generalise to the following notions. Let , k ≥ 1 be two integers, and G be a graph. To each edge of G, we assign, via a colouring ω, a pair (α, β), where α ∈ {1, . . . , } and β ∈ {1, . . . , k}, which can be regarded as a coloured weight (with colour α and value β). For simplicity, this ω is what we call an ( , k)-colouring of G. Now, for every vertex v of G, and every colour α ∈ {1, . . . , }, one can compute the weighted α-degree σ α (v), being the sum of weights with colour α incident to v. So, to every vertex v is associated a palette (σ 1 (v), . . . , σ (v)) of coloured weighted degrees.

When working on variants of the 1-2-3 Conjecture, the intent is to design edge-weightings ω that allow to distinguish the adjacent vertices, accordingly to some distinction condition. When dealing with the notions introduced in the last paragraph, there are many ways for asking for distinction, as several "coloured sums" are available; in [START_REF] Baudon | A general decomposition theory for the 1-2-3 Conjecture and locally irregular decompositions[END_REF], we focused on the following three distinction variants, which sounded the most natural to us:

Contributions aux pondérations distinguantes de graphes

Résumé :

Ce document décrit certains des travaux que j'ai menés depuis la soutenance de ma thèse de doctorat en juin 2014 à l'Université de Bordeaux. Il se concentre plus particulièrement sur mes contributions aux pondérations distinguantes de graphes et à la 1-2-3 Conjecture, qui occupe une place centrale dans ce domaine. L'objectif principal pour ce type de problèmes est, étant donné un graphe, de pondérer ses arêtes de sorte que les sommets voisins soient distinguables vis-à-vis d'un paramètre induit par la pondération. Par exemple, la 1-2-3 Conjecture, posée par Karoński, Łuczak et Thomason en 2004, dit que tout graphe peut être pondéré avec 1, 2, 3 de sorte que les sommets voisins soient distinguables par leurs sommes de poids incidents.

Bien que la 1-2-3 Conjecture n'ait originellement été introduite que comme un problème artificiel, plusieurs résultats obtenus lors des dernières années ont montré que sa nature est en fait plus profonde. De par sa définition même, cette conjecture a clairement une nature algébrique. Des résultats récents montrent qu'elle a également une nature décompositionnelle. Il existe également des liens étroits entre la 1-2-3 Conjecture et des notions fondamentales de théorie des graphes, comme les colorations propres de sommets.

Dans ce document sont présentés des résultats permettant de conforter cette nature des pondérations distinguantes. Deux chapitres sont proposés :

• Dans un premier chapitre, nous présentons des résultats sur plusieurs aspects de la 1-2-3

Conjecture. Ces résultats portent à la fois sur des aspects principaux de la conjecture, i.e., qui font progresser notre connaissance sur certaines de ses questions ouvertes principales, et sur des aspects plus annexes, i.e., qui permettent de comprendre davantage sa nature profonde. Ces aspects annexes incluent des questions liées à la vraie importance des poids 1, 2, 3 dans la 1-2-3 Conjecture, aux conséquences de demander une distinction plus franche entre les voisins, et à des généralisations de la conjecture aux graphes dirigés.

• Dans un second chapitre, nous présentons des résultats sur les décompositions localement irrégulières de graphes, qui sont un type de décompositions attestant de la nature décompositionnelle de la 1-2-3 Conjecture. Ces résultats incluent des améliorations de résultats décompositionnels connus, ainsi qu'une théorie permettant de réunir la 1-2-3 Conjecture et les décompositions localement irrégulières au sein d'un même contexte.

Chacun des deux chapitres se termine par une conclusion décrivant l'impact de nos résultats sur le domaine, ainsi que des perspectives de recherche que nous avons pour le futur.

Mots-clefs :

pondérations distinguantes ; 1-2-3 Conjecture ; décompositions localement irrégulières ; décompositions de graphes ; colorations de graphes.

Université Côte d'Azur

28 Avenue Valrose 06100 Nice, France