Julien Bensmail

Hervé Hocquard

Pierre-Marie Marcille

On inducing degenerate sums through 2-labellings

Keywords: 1-2-3 Conjecture, degenerate sum, 2-labelling, vertex-arboricity

We deal with a variant of the 1-2-3 Conjecture introduced by Gao, Wang, and Wu in 2016. This variant asks whether all graphs can have their edges labelled with 1 and 2 so that when computing the sums of labels incident to the vertices, no monochromatic cycle appears. In the aforementioned seminal work, the authors mainly verified their conjecture for a few classes of graphs, namely graphs with maximum average degree at most 3 and series-parallel graphs, and observed that it also holds for simple classes of graphs (cycles, complete graphs, and complete bipartite graphs).

In this work, we provide a deeper study of this conjecture, establishing strong connections with other, more or less distant notions of graph theory. While this conjecture connects quite naturally to other notions and problems surrounding the 1-2-3 Conjecture, it can also be expressed so that it relates to notions such as the vertex-arboricity of graphs. Exploiting such connections, we provide easy proofs that the conjecture holds for bipartite graphs and 2-degenerate graphs, thus generalising some of the results of Gao, Wang, and Wu. We also prove that the conjecture holds for graphs with maximum average degree less than 10 3 , thereby strengthening another of their results. Notably, this also implies the conjecture holds for planar graphs with girth at least 5. All along the way, we also raise observations and results highlighting why the conjecture might be of greater interest.

Introduction

Let G be a graph, and ℓ be a k-labelling of G, i.e., an assignment of labels from {1, . . . , k} to the edges of G. For every vertex v of G, we define the sum of v (w.r.t. ℓ), denoted by σ ℓ (v) (or, when no confusion is possible, simply by σ(v)), as the value ∑ u∈N (v) ℓ(vu), being the sum of the labels assigned by ℓ to the edges incident to v. In case we have σ(u) ≠ σ(v) for every edge uv of G, thus for every two adjacent vertices u and v, we say that ℓ is proper. We define χ Σ (G) as the smallest k ≥ 1 such that proper k-labellings of G exist (if any).

Through inductive arguments, it is not too complicated to prove that χ Σ (G) is always defined, provided G does not contain K 2 , the complete graph on two vertices, as a connected component. The other way round, it is clear that K 2 does not admit any proper labelling. For these reasons, the previous notions and parameters are more commonly investigated for nice graphs, which are those graphs with no K 2 as a connected component.

We now have all notions in hand to recall the so-called 1-2-3 Conjecture introduced by Karoński, Łuczak, and Thomason in 2004 (in [START_REF] Karoński | Edge weights and vertex colours[END_REF]), which suggests an absolute constant upper bound on χ Σ (G) for all nice graphs G. It reads as follows:

1-2-3 Conjecture. If G is a nice graph, then χ Σ (G) ≤ 3.

The 1-2-3 Conjecture has been receiving quite some attention over the years, several of its aspects being investigated in dedicated series of works. Regarding the very conjecture itself, it has to be known that graphs G with χ Σ (G) = 3 exist (so the conjecture, if true, would be best possible, see e.g. [START_REF] Dudek | On the complexity of vertex-coloring edge-weightings[END_REF]), that the conjecture holds for 3-colourable graphs (see [START_REF] Karoński | Edge weights and vertex colours[END_REF]), and that χ Σ (G) ≤ 5 was proved to hold for every nice graph G (see [START_REF] Kalkowski | Vertex-coloring edge-weightings: towards the 1-2-3 Conjecture[END_REF]). tree-colouring edge 2-weighting. They lastly observe that a e Σ (G) = 1 if and only if G is a graph with no cycle in which all vertices have the same degree.

As mentioned earlier, our main goal in the current paper is to revisit the notions, results, and main conjecture from [START_REF] Gao | A Relaxed Case on 1-2-3 Conjecture[END_REF], and, in particular, to show how they relate to known notions of graph theory, from both the very field surrounding the 1-2-3 Conjecture and the more general chromatic theory. Most of this we achieve in Section 2, in which we make more explicit the connection between tree-colourings, tree-colouring edge weightings, and the well-known notion of vertex-arboricity. In particular, we show how to exploit this connection to prove the conjecture of Gao, Wang, and Wu for wider classes of graphs; notably, this leads us to proving the conjecture for bipartite graphs and 2-degenerate graphs in Section 3, thereby providing easier proofs for some of the results from [START_REF] Gao | A Relaxed Case on 1-2-3 Conjecture[END_REF]. Through an ad hoc proof, we then also prove this conjecture for graphs with maximum average degree less than 10 3 , improving another result from [START_REF] Gao | A Relaxed Case on 1-2-3 Conjecture[END_REF], and deducing side results (in particular, the conjecture holds for planar graphs with girth at least 5). We finish off this work in concluding Section 5, in which we discuss other connections between the conjecture of Gao, Wang, and Wu and other problems related to the 1-2-3 Conjecture. In particular, we come up with new problems, and directions for further work on the topic.

2. Revisiting the notions and conjecture from [START_REF] Gao | A Relaxed Case on 1-2-3 Conjecture[END_REF] We start off with the straight observation that the notion of tree-colouring from [START_REF] Gao | A Relaxed Case on 1-2-3 Conjecture[END_REF] is nothing but the colouring notion behind the so-called vertex-arboricity parameter, which was introduced as early as in the 1960s, by Chartrand, Kronk, and Wall [START_REF] Chartrand | The point-arboricity of a graph[END_REF]. It is important to point out that all notions behind this parameter have received a lot of attention throughout the years, and, in particular, that the terminology used by researchers has been quite inconsistent; thus, the reader must be aware that the upcoming notions and terminology might vary a lot from those used in other works on the same topic.

A degenerate k-colouring of a graph G is a partition of its vertex set V (G) into k parts V 1 , . . . , V k such that each colour class V i induces a forest G[V i ], i.e., an acyclic graph (or, in other words, a graph with degeneracy 1, hence the term "degenerate"). Note that this notion is precisely that of tree-colouring from [START_REF] Gao | A Relaxed Case on 1-2-3 Conjecture[END_REF]. The vertex-arboricity of G, denoted by a(G), is the smallest k ≥ 1 such that G admits degenerate k-colourings. Clearly, we always have a(G) ≤ χ(G), and thus a(G) is always well defined. Now, we say that a labelling ℓ of G is degenerate if the sum function σ ℓ indeed stands as a degenerate colouring of G. Note that this is equivalent to saying that, by σ ℓ , there is no x-cycle1 , i.e., no cycle v 1 . . . v p v 1 with σ(v 1 ) = ⋅ ⋅ ⋅ = σ(v p ) = x for some x ∈ N + . We denote by χ d Σ (G) the smallest k ≥ 1, if any, such that degenerate k-labellings of G exist. Note that our notion of degenerate labelling is exactly that of tree-colouring edge weighting from [START_REF] Gao | A Relaxed Case on 1-2-3 Conjecture[END_REF], and similarly our parameter χ d Σ is exactly a e Σ from there. Using this modified terminology, we can now restate the main conjecture from [START_REF] Gao | A Relaxed Case on 1-2-3 Conjecture[END_REF]:

Conjecture 2.1. If G is a graph, then χ d Σ (G) ≤ 2.
Before proceeding with more relevant observations, let us establish formally a few facts on Conjecture 2.1. First, note that degenerate labellings can be perceived as a weakening of proper labellings, in that proper colourings are all degenerate (but the opposite, obviously, is not always true). From this, we deduce that χ d Σ (G) ≤ χ Σ (G) holds for every nice graph G, which means that Conjecture 2.1 holds for all graphs G with χ Σ (G) ≤ 2. We do not get much from this, however, as it is known that graphs G with χ Σ (G) ≤ 2 cannot be described in an "easy way", unless P = NP (see [START_REF] Dudek | On the complexity of vertex-coloring edge-weightings[END_REF]), and this remains true even for cubic graphs [START_REF] Ahadi | Algorithmic complexity of proper labeling problems[END_REF]. On the other hand, bipartite graphs G with χ Σ (G) ≤ 2 are easy to describe [START_REF] Thomassen | The 3-flow conjecture, factors modulo k, and the 1-2-3-conjecture[END_REF], but, as will be seen later on in Section 3, this fact is not necessary to prove that bipartite graphs comply with Conjecture 2.1. As a final remark, note that, in the context of Conjecture 2.1, no notion of niceness is required, as it can easily be observed that all graphs admit degenerate labellings (this follows e.g. from the fact that χ d Σ (G) ≤ χ Σ (G) holds for every nice graph G, and that we obviously have χ d Σ (K 2 ) = 1 since K 2 is a tree). At this point, note that the previous statements barely bring anything particularly new regarding Conjecture 2.1. The more crucial point we will build upon, is that there is actually a strong connection between degenerate colourings and degenerate labellings, in that a degenerate colouring can serve as a "layout" to design a degenerate labelling, provided we are allowed to use labels with sufficiently high magnitude. This fact being actually very common when it comes to designing distinguishing labellings (see e.g. [START_REF] Bensmail | An injective version of the 1-2-3 Conjecture[END_REF] and the references pointed therein), we recall the notions involved behind this statement.

Let G be a graph, and ϕ be a k-colouring of G with parts V 0 , . . . , V k-1 , where the V i 's do not have to fulfil particular properties (in particular, ϕ does not have to be proper or degenerate). We say that a labelling ℓ of G matches ϕ modulo k if we have σ(v) ≡ ϕ(v) mod k for every vertex v of G. The crucial point is that if ℓ matches ϕ modulo k and ϕ has particular properties, then we can derive corresponding properties onto ℓ. For instance, if ϕ is proper or degenerate, then, under that condition, ℓ is also proper or degenerate, respectively. A tricky point, however, as mentioned above, is that designing ℓ so that it matches ϕ modulo k might require ℓ to assign sufficiently large labels. Fortunately, this is a well studied approach, and the following result was established: Theorem 2.2 (see e.g. Theorems 3.7 to 3.9 in [START_REF] Bensmail | An injective version of the 1-2-3 Conjecture[END_REF]). Let G be a nice connected graph, and ϕ be a k-colouring of G with parts V 0 , . . . , V k-1 . Then:

• if G is not bipartite and k / ≡ 2 mod 4, then G admits k-labellings matching ϕ modulo k;

• otherwise, G admits (k + 1)-labellings matching ϕ modulo k + 1.

As pointed out in [START_REF] Bensmail | An injective version of the 1-2-3 Conjecture[END_REF], unfortunately Theorem 2.2 cannot be improved in general. Still, in the context of degenerate labellings, we derive the following as a corollary:

Corollary 2.3. If G is a nice connected graph, then: • χ d Σ (G) ≤ a(G) if G is not bipartite and a(G) / ≡ 2 mod 4, and
• χ d Σ (G) ≤ a(G) + 1 otherwise.
While Corollary 2.3 is interesting in itself, the unfortunate point is that, in the context of Conjecture 2.1, the most interesting use of Corollary 2.3 would be for graphs with vertexarboricity 2, which is precisely one of the bad cases of the corollary. As will be showcased in Section 3, there are ways to circumvent this issue in particular contexts. Be aware that, in any case, determining if a graph has vertex-arboricity 2 is NP-complete (see [START_REF] Hakimi | A note on the vertex arboricity of a graph[END_REF]). Now that it should be clear why degenerate colourings might be interesting to consider in the context of Conjecture 2.1, we survey two known facts on the vertex-arboricity of graphs2 . These facts deal with the vertex-arboricity of graphs with bounded maximum degree, standing as a Brooks-like result, and graphs with bounded degeneracy.

Theorem 2.4 ([17]

). Let G be a connected graph. If G is neither a cycle nor a complete graph with odd order, then a(G) ≤ ⌈

∆(G) 2 ⌉. Theorem 2.5 ([20]). If G is a k-degenerate graph, then a(G) ≤ ⌈ k+1
2 ⌉ In the context of Conjecture 2.1 and Corollary 2.3, note that these two results are mostly interesting for graphs with maximum degree at most 4 and graphs with degeneracy at most 3, since they have vertex-arboricity at most 2 in general.

Conjecture 2.1 for bipartite graphs and 2-degenerate graphs

In this section, we go beyond some of the results from [START_REF] Gao | A Relaxed Case on 1-2-3 Conjecture[END_REF] by proving Conjecture 2.1 for bipartite graphs and 2-degenerate graphs. In particular, our result for bipartite graphs covers that for complete bipartite graphs in [START_REF] Gao | A Relaxed Case on 1-2-3 Conjecture[END_REF], while our result for 2-degenerate graphs covers that for series-parallel graphs and most of that for graphs with maximum average degree at most 3 (as only the ones with cubic connected components are not 2-degenerate). Again, an important point is that the proof arguments we employ, which are based on the notions developed in Section 2, are much simpler than those employed in [START_REF] Gao | A Relaxed Case on 1-2-3 Conjecture[END_REF], and more reminiscent of classical tools and arguments used in the whole field. For both graph classes, we mainly use the fact that their vertex-arboricity is at most 2.

We consider bipartite graphs first, before focusing on 2-degenerate graphs.

Theorem 3.1. If G is a bipartite graph, then χ d Σ (G) ≤ 2.
Proof. We can assume G is connected. Let ϕ be a proper {0, 1}-colouring of G. Choose any vertex v of G. Starting from all edges of G assigned label 2, we consider all vertices u in V (G) ∖ {v} in turn, and, if σ(u) / ≡ ϕ(u) mod 2, swap any path P joining u and v. That is, we turn all 1's assigned to the edges of P into 2's, and vice versa. Note that this has the effect of altering the parity of the sums of u and v only; thus, now σ(u) ≡ ϕ(u) mod 2. Once all vertices u have been treated, by the resulting labelling ℓ we thus have σ(u) ≡ ϕ(u) mod 2 for all u ∈ V (G) ∖ {v}. If also σ(v) ≡ ϕ(v) mod 2, then ℓ actually matches ϕ modulo 2, and ℓ is not only degenerate but also proper. Otherwise, σ must be degenerate, as all pairs of adjacent vertices with the same sum include v, and G is bipartite.

Theorem 3.2. If G is a 2-degenerate graph, then χ d Σ (G) ≤ 2.
Proof. We can suppose G is connected. Let v be a vertex of G with d(v) ≤ 2, and ϕ be a degenerate {0, 1}-colouring of G, which exists by Theorem 2.5. Starting from all edges of G being assigned label 2, we consider all vertices u in V (G) ∖ {v} in turn, and, if σ(u) / ≡ ϕ(u) mod 2, swap any path joining u and v. As in the proof of Theorem 3.1, once all vertices u ∈ V (G) ∖ {v} have been treated this way, we obtain a 2-labelling ℓ of G that matches ϕ modulo 2, except maybe because of v. If ℓ matches ϕ modulo 2, then we are done. So, suppose ℓ does not match ϕ modulo 2. If d(v) = 1, then, because no cycle of G contains v, we have that ℓ must be degenerate. Otherwise, assume d(v) = 2, and denote by v 1 and v 2 the two neighbours of v. If ℓ is not degenerate, then σ(v) = σ(v 1 ) = σ(v 2 ), and the three values have the same parity, which, free to switch colours by ϕ and swap paths again, can be assumed to be odd. Precisely, since d(v) = 2, we must have σ(v) = 3, and, thus, say, ℓ(vv 1 ) = 1 and ℓ(vv 2 ) = 2. Then, so that σ(v) = σ(v 2 ), we must have d(v 2 ) = 2, and the second edge incident to v 2 must be assigned label 1. Change the label assigned to vv 2 to 1. By the resulting 2-labelling, note that we now have σ(v) = σ(v 2 ) = 2, while we still have σ(v 1 ) = 3. Since d(v) = d(v 2 ) = 2, this labelling is thus degenerate. Particularly, observe that these arguments hold regardless of whether v 1 and v 2 are adjacent.

4. Conjecture 2.1 for graphs with maximum average degree less than 10 3 Recall that the average degree ad(G) of a graph G is defined as

2|E(G)|
|V (G)| , while the maximum average degree mad(G) of G is the maximum value of the average degree ad(H) over all subgraphs H of G. As mentioned earlier, the authors of [START_REF] Gao | A Relaxed Case on 1-2-3 Conjecture[END_REF] proved Conjecture 2.1 for graphs with maximum average degree at most 3. We improve this result by showing that Conjecture 2.1 holds for graphs with maximum average degree less than 10 3 .

Theorem 4.1. If G is a graph with mad(G) < 10 3 , then χ d Σ (G) ≤ 2.
We prove Theorem 4.1 through the so-called discharging method, which consists of two main steps. Assuming Theorem 4.1 is wrong, we consider a minimum counterexample to the claim, that is, a smallest (in terms of number of vertices and edges) graph G with mad(G) < 10 3 and

χ d Σ (G) > 2.
We then aim at proving that G cannot actually exist. Towards this goal, as a first step we start by proving that G cannot contain certain configurations, i.e., particular subgraphs, as otherwise we could remove some elements (vertices and/or edges) from G to end up with a graph G ′ which, by the minimality of G, would admit degenerate 2-labellings that we could extend to G, a contradiction to G being a counterexample to Theorem 4.1. We then end up with a set S of sparse structures that cannot appear in G, assuming it is a minimum counterexample. In a second step, we then show that G, because of its sparseness (since mad(G) < 10 3 ), must actually contain at least one of the configurations in S, thereby reaching a final contradiction.

The second step above is commonly achieved through a certain discharging process. In such a process, we define a charge function ω ∶ V (G) → R through which every vertex v of G gets assigned some initial charge ω(v). The process then consists in "moving" charges from vertices to vertices, according to some well-defined discharging rules, resulting in a new charge function ω ′ . The goal is to define S, ω, and the discharging process (that is, its discharging rules) so that, eventually, we can deduce that the total amount of charges by ω is not the same as by ω ′ , which is not possible since, through a discharging process, charges are being moved, but no charges are supposed to be created or lost.

In our proof of Theorem 4.1, we enhance the discharging method with the so-called ghost vertices method (introduced formally in [START_REF] Bonamy | Adjacent vertex-distinguishing edge coloring of graphs[END_REF]), which, in the context of graphs with bounded maximum average degree, provides a way, through some discharging process, to establish that a graph has large maximum average degree. Theorem 4.2 (see e.g. [START_REF] Bonamy | Global discharging methods for coloring problems in graphs[END_REF]). Let G be a graph, m be some value, and (V 1 , V 2 ) be any partition of V (G). Let also ω be a charge function where ω(v) = d(v) -m for every v ∈ V (G). If there is a discharging process resulting in a charge function ω * where

• ω * (v) ≥ 0 for every v ∈ V 1 , and • ω * (v) ≥ ω(v) + d V 1 (v) for every v ∈ V 2 , then mad(G) ≥ m.
Before proceeding with the proof of Theorem 4.1, we need to introduce some terminology and auxiliary results beforehand. In what follows, for any k ≥ 0, a vertex v of a graph is called a k

-vertex if d(v) = k, a k --vertex if d(v) ≤ k, and a k + -vertex if d(v) ≥ k. Similarly, a neighbour u of v is called a k-neighbour of v if u is a k-vertex, a k --neighbour of v if u is a k --vertex, and a k + -neighbour of v if u is a k + -vertex.
Let us recall the obvious fact that adjacent vertices with sufficiently different degrees cannot get the same sum by any 2-labelling of a graph. Particularly, by a 2-labelling, the next result implies that a 2-vertex and an adjacent 4 + -vertex cannot have the same sum, and similarly for a 3-vertex and an adjacent 6 + -vertex. Also, a 1-vertex can only have the same sum as its unique neighbour if that vertex is also a 1-vertex.

Observation 4.3. Let G be a graph, and u and v be a p-vertex and a q-vertex, respectively, being adjacent in G. By any 2-labelling ℓ of G, if p > 2q -1, then σ(u) > σ(v).

Proof. Set x u = σ(u) -ℓ(uv) and x v = σ(v) -ℓ(uv). Then, so that σ(u) = σ(v), we must have x u = x v , which is impossible as we have x u ≥ p -1 and x v ≤ 2(q -1), but p > 2q -1.

We now introduce some terminology and results that relate to degenerate labellings. Let G be a graph. For a set S ⊆ V (G) of vertices of G, we denote by N * (S) the set of the vertices of V (G) ∖ S that have at least one neighbour in S. Given two disjoint subsets X, Y of V (G), we denote by E(X, Y ) the set of edges joining a vertex of X and one of Y .

Assuming W is a connected induced subgraph of G, we denote by G ∖ e W the subgraph G -E(W ). For any 2-labelling ℓ of G ∖ e W , by extending ℓ to G we mean keeping, in G, all edges of E(G ∖ e W ) being labelled as labelled by ℓ, and assigning labels (from {1, 2}) to all edges of W . The resulting 2-labelling is called an extension of ℓ, from G ∖ e W to G.

Let again ℓ be a 2-labelling of G∖ e W . We call a set C ⊆ N * (V (W )) of vertices of G∖ e W a frontier (w.r.t. ℓ) for W if, for every extension of ℓ to G, any vertex of W contained in an x-cycle (if any) must have its two neighbours in that cycle lying in C ∪ V (W ). A vertex of a given frontier C for W is said small if it has only one neighbour in W , while it is said big otherwise, i.e., if it has at least two neighbours in W (recall that C ⊆ N * (V (W )), and thus, indeed, every vertex of C has neighbours in W ). For a vertex v in W , a value x ≥ 1 is said forbidden if there exists an extension of ℓ to G for which v belongs to an x-cycle.

The next result connects the previous notions, as it provides, in certain contexts, bounds on the number of forbidden values for a vertex when extending a degenerate 2-labelling of some G ∖ e W to the edges of a subgraph W . Particularly, we consider contexts where x-cycles by an extension cannot be fully contained in W , and either 1) can "traverse" W , i.e., contain edges of W , or 2) can only "touch" W , i.e., contain vertices but no edges of W .

Lemma 4.4. Let G be a graph, W be a connected induced subgraph of G, ℓ be a degenerate 2-labelling of G ∖ e W , u be a vertex of W , and C be a frontier for W . Assume F denotes the set of forbidden values for u; the following upper bounds on |F | hold.

(1) If, by every extension of ℓ to G, every x-cycle containing u is not contained in W and, thus, necessarily contains a vertex not in W , then

|F | ≤ |E(V (W ),C)| 2 .
(2) If, by every extension of ℓ to G, every x-cycle containing u is not contained in W and does not contain any other vertex of W , then

|F | ≤ |C| 2 .
Particularly, in both contexts, if σ(u) can reach strictly more than |F | values through extending ℓ to G, then there is one extension where u is not contained in a σ(u)-cycle.

Proof. Recall that, by the definition of a frontier, in both contexts if u is contained in a σ(u)-cycle when extending ℓ to G (thus to the edges of W ), then the two neighbours of u in that cycle must belong to C ∪ V (W ). From this, (2) clearly holds. Recall indeed that if ℓ ′ is an extension of ℓ to G, then σ ℓ (v) = σ ℓ ′ (v) for any v ∈ V (G) ∖ V (W ). Now, since any x-cycle containing u by an extension of ℓ must contain vertices of V (G) ∖ V (W ) ∪ {u} only, then, for every forbidden value x ∈ F for u, there must be at least two neighbours of

u in C with sum x. Then, |F | ≤ |C| 2 .
We now focus on proving [START_REF] Ahadi | Algorithmic complexity of proper labeling problems[END_REF]. We first claim that

|F | ≤ |{v : v is a small vertex of C}| 2 + |{v : v is a big vertex of C}|.
Indeed, let x ∈ F be a forbidden value for u. It can be noted that either there are at least two small vertices with sum x in C, or there is at least one big vertex with sum x in C. Indeed, since x is forbidden, there exists an extension ℓ ′ of ℓ to G such that σ ℓ ′ (u) = x and u is contained in an x-cycle Q that does not contain vertices of W only (hypothesis of the statement). It is important to note, again, that, for every vertex v ∈ C, we have

σ ℓ (v) = σ ℓ ′ (v), i.e.
, labelling the edges of W does not alter the sums of the vertices in C. Let now P be the maximum sequence of consecutive vertices of Q that contains u and vertices of W only, that is, if

Q = (v 0 , . . . , v k-1 , v 0 ), then P = (v α , . . . , v β ) where v α , . . . , v β ∈ V (W ) and v aα-1 , v β+1 / ∈ V (W ) (
where operations over the subscripts are modulo k), and we have u ∈ {v α , . . . , v β }. Possibly, P = (u), in which case u = v α = v β . By definition of a frontier, and because

Q does not contain vertices of W only, v = v α-1 and v ′ = v β+1 lie in C. If v = v ′ , then v is a big vertex.
Otherwise, v and v ′ are different, and either one of them is a big vertex, or both are small. We thus have our desired conclusion for x, and since this holds independently for every forbidden value x ∈ F , the inequality on |F | above holds.

Let us now denote by n the number of small vertices of C, and by m the number of big vertices of C. Then, |C| = n + m. Also, by the previous inequality, we thus have

|F | ≤ n 2 + m. Now,
+ m = |C| ≤ |E(V (W ), C)| -m, thus that n + 2m ≤ |E(V (W ), C)|, and hence |F | ≤ n 2 + m ≤ |E(V (W ), C)| 2 ,
as desired.

We are now ready for our proof of Theorem 4.1.

Proof of Theorem 4.1. As mentioned earlier, we prove the result through the discharging method. Assume Theorem 4.1 is wrong, and let G be a counterexample to the claim that is minimum w.r.t.

|V (G)| + |E(G)|. That is, mad(G) < 10 3 and χ d Σ (G) > 2,
and G is one of the smallest graphs with these properties. In particular, whenever removing elements from G, we get a smaller graph that complies with Theorem 4.1 (particularly, no subgraph of G has average degree at least 10 3 , as otherwise we would have mad(G) ≥ 10 3 ). Also, the minimality of G implies that G can be assumed connected. We assume also G is not K 2 .

We start by proving that G cannot contain certain configurations, given that G is a minimum counterexample to Theorem 4. 1. In what follows, when saying that G fulfils some property because of Configuration Ci, it should be understood that this is because, otherwise, G would contain some structure contradicting the ith item (Ci) of Claim 4.5. (C7) a 4-vertex adjacent to three 3-vertices, one of which has two 3-neighbours;

(C8) a (3d 1 +d 2 +1) --vertex of degree at least 6 adjacent to d 1 2 --vertices and d 2 3-vertices.

Proof of the claim. Throughout the proof, in several occasions we will find ourselves in situations where, through 2-labelling the edges of G one by one, we need to consider assigning a label to some edge uv where v is a 3-vertex with neighbours u, w 1 , and w 2 , and, earlier in the labelling process, all edges incident to w 1 and w 2 (in particular vw 1 and vw 2 ) have already been assigned a label, meaning that σ(w 1 ) and σ(w 2 ) are fixed. Note that, upon assigning a label to uv, we also fix σ(v), which, depending on the choice we made for uv, might result in x-cycles containing u and/or v. In particular, we say that v is bad if we have σ(w 1 ) = σ(w 2 ). If v is bad, then, when labelling uv, if σ(v) = σ(w 1 ) = σ(w 2 ), this might result in v belonging, together with w 1 and w 2 , to an x-cycle. However, if v is bad, then we note that there is at least one label in {1, 2}, which we call a fitting label, which, when assigned to uv, guarantees that σ(v) ≠ σ(w 1 ), σ(w 2 ), and, thus, that no x-cycle can eventually contain v. On the other hand, we say that v is good if σ(w 1 ) ≠ σ(w 2 ). This time, upon labelling uv, note that the resulting σ(v) might be equal to at most one of the values in {σ(w 1 ), σ(w 2 )}. As a result, if, eventually, x-cycles containing v exist, then they must contain u and exactly one of w 1 and w 2 .

We now deal with each of the configurations one by one.

• Configuration C1.

Assume G contains a 2 --vertex u adjacent to a 4 --vertex v. Consider W , the induced subgraph of G with edge set {uv}. By minimality of G, there is a degenerate 2labelling ℓ of G ∖ e W , which we wish to extend to G (thus by assigning a label in {1, 2} to uv). We split the proof into a few cases.

-If v is a 4-vertex or u is a 1-vertex, then, by Observation 4.3, note that, whatever label we assign to uv, we cannot have σ(u) = σ(v). This means that if an x-cycle appears, then it must contain v and cannot contain u. Then, C = N (v) ∖ {u} is a frontier for W with |C| ≤ 3. By Lemma 4.4(2), there is a degenerate extension of ℓ to G, since, upon 2-labelling, uv, we can alter σ(v) in two ways.

-If u and v are both 2-vertices, then let us denote by u ′ and v ′ their other respective neighbour (i.e., uu ′ and vv ′ are edges of G). Possibly, u ′ = v ′ . * If ℓ(uu ′ ) ≠ ℓ(vv ′ ), then, whatever label we assign to uv, we cannot have σ(u) = σ(v). Furthermore, since |N (u) ∖ {v}| = |N (v) ∖ {u}| = 1, no x-cycle can be created upon labelling uv. Thus, a degenerate 2-labelling of G is obtained from ℓ when assigning any label to uv. * If ℓ(uu ′ ) = ℓ(vv ′ ), then we assign to uv a label in {1, 2} so that σ(u) ≠ σ(u ′ ). This way, no x-cycle can contain u, and thus no x-cycle can contain v. Also, since, again, |N (u) ∖ {v}| = |N (v) ∖ {u}| = 1, no x-cycle can exist at all, and we thus end up with a degenerate 2-labelling of G.

-The last case is when u is a 2-vertex and v is a 3-vertex. * Assume first u and v share a common neighbour w. We extend ℓ to G by first assigning label 1 to uv. If no x-cycle is created, then we are done. Otherwise, there is some x-cycle (containing u and/or v).

• If some x-cycle contains u, then it also contains v and w. Then change the label of uv to 2. This way, note that σ(u) = σ(v) ≠ σ(w), and no more x-cycle remains. Then a degenerate 2-labelling of G is obtained. • Otherwise, there is an x-cycle containing v, w, and w ′ , the third neighbour of v different from u and w. Again, change the label assigned to uv to 2. As a result, we get σ(v) ≠ σ(w) = σ(w ′ ), and, thus, no x-cycle can remain. Then, we get a degenerate 2-labelling of G. * Otherwise, if u and v do not share a common neighbour, then note that v is either good or bad. Let u ′ denote the neighbour of u different from v.

• If v is bad, then we assign a fitting label in {1, 2} to uv. This way, the only neighbour of v that might have sum σ(v) is u, which makes it impossible for u and v to belong to any x-cycle. Thus, we are done. • If v is good, then we assign a label in {1, 2} to uv chosen so that σ(v) ≠ σ(u ′ ). This makes it impossible for u and v to belong to any x-cycle (in particular, the fact that v was good in the first place means at most one of its two neighbours different from u has sum σ(v)). Then, again, we end up with a degenerate 2-labelling of G.

• Configuration C2.

Assume G contains a 3-vertex u adjacent to three 3-vertices v 1 , v 2 , and v 3 . We consider a few cases, depending on the edges that the subgraph

G[{v 1 , v 2 , v 3 }] possesses. -|E(G[{v 1 , v 2 , v 3 }])| = 3.
In that case, note that G is actually K 4 , the complete graph on four vertices, a graph which is known to admit degenerate 2-labellings, see [START_REF] Gao | A Relaxed Case on 1-2-3 Conjecture[END_REF]. For instance, a degenerate 2-labelling is obtained when assigning label 2 to uv 1 , and label 1 to the other five edges (two vertices get sum 3, while the other two get sum 4).

-

|E(G[{v 1 , v 2 , v 3 }])| = 2. Assume the two edges are v 1 v 2 and v 2 v 3 . Set H = G -{uv 1 , uv 2 , uv 3 , v 1 v 2 , v 2 v 3 }.
By minimality of G, there is a degenerate 2-labelling of H, which we extend to G by assigning labels in {1, 2} to uv 1 , uv 2 , uv 3 , v 1 v 2 , and v 2 v 3 . Start by assigning label 1 to uv 1 , uv 2 , and uv 3 , and label 2 to v 1 v 2 and v 2 v 3 . As a result, σ(u) = 3, σ(v 2 ) = 5, and σ(v 1 ), σ(v 3 ) ≥ 4. If no x-cycle results, then we are done. Otherwise, it must be that σ(v 1 ) = σ(v 2 ) = σ(v 3 ) = 5, and there is a 5-cycle containing v 1 , v 2 , and v 3 . In particular, for each of v 1 and v 3 , the only incident edge going to a vertex not in {u, v 2 } is assigned label 2 by ℓ. Here, change to 2 the label assigned to uv 2 . As a result, we still have σ(v 1 ) = σ(v 3 ) = 5, but σ(u) = 4 and σ(v 2 ) = 6. The resulting 2-labelling of G is thus degenerate.

- and label 2 to v 1 v 2 . As a result, σ(u) = 3, while σ(v 1 ), σ(v 2 ) > 3. This means that if the resulting 2-labelling of G is not degenerate, then it must be because of v 1 and v 2 which belong to the same x-cycle (also containing their unique neighbours not in {v 1 , v 2 , u}). Then change to 2 the label assigned to uv 1 and uv 2 . This time, if the attained 2-labelling is still not degenerate, then note that the only possible x-cycle must be v 1 v 2 uv 1 , since σ(v 1 ) and σ(v 2 ) are larger than the sums of the unique neighbours of v 1 and v 2 not in {v 1 , v 2 , u}. If this x-cycle exists, then change to 2 the label assigned to uv 3 . As a result, we now have σ(v 1 ), σ(v 2 ) < σ(u), and thus neither u nor v 3 can be involved in an x-cycle. Particularly, recall that v 3 was good. Thus, the resulting 2-labelling of G is degenerate.

|E(G[{v 1 , v 2 , v 3 }])| = 1. Assume the only edge is v 1 v 2 . Consider H = G -{uv 1 , uv 2 , uv 3 , v 1 v 2 },
-

|E(G[{v 1 , v 2 , v 3 }])| = 0.
In this case, W , the subgraph of G with edge set {uv 1 , uv 2 , uv 3 }, is an induced subgraph. Let ℓ be a degenerate 2-labelling of G∖ e W , which exists by minimality of G. Particularly, each v i is either good or bad. Recall that, upon assigning a fitting label in {1, 2} by an extension of ℓ to some uv i under the assumption that v i is bad, then no x-cycle can eventually contain v i . We start extending ℓ to G by assigning a fitting label in {1, 2} to every edge uv i such that v i is bad. If no uv i remains to be labelled, that is, all v i 's were bad, then we end up with a degenerate 2-labelling of G (since no v i can belong to an x-cycle, and thus neither can u). Otherwise let R be the induced subgraph of G (and, actually, of W ) containing the edges that remain to be labelled, thus the edges uv i where v i is good. So -If w is bad, then we start by assigning a fitting label in {1, 2} to uw. As a result, recall that w cannot be contained in an x-cycle, whatever label we assign to uv. Note also that, by Observation 4. -If w is good, then if an x-cycle containing w appears when extending ℓ to G, then that cycle must contain u. Recall also that u and v cannot have the same sum by a 2-labelling, according to Observation 4.3, meaning that v cannot be contained in an x-cycle at all. Meanwhile, upon 2-labelling uv and vw, we can alter σ(u) in three possible ways. There is thus a way to 2-label those edges so that the sum of u is the same as that of at most one of the at most five vertices in N (u) ∪ N (w) ∖ {u, v, w}. This results in a degenerate extension of ℓ to G.

• Configuration C5.

Assume G contains a 4-vertex u adjacent to four 3-vertices v 1 , v 2 , v 3 , and v 4 . We split the proof into a few cases, depending on the edges in the subgraph

G[{v 1 , v 2 , v 3 , v 4 }].
-

|E(G[{v 1 , v 2 , v 3 , v 4 }])| = 4.
In this case, we have the edges

v 1 v 2 , v 2 v 3 , v 3 v 4
, and v 4 v 1 , and G is a wheel of order 5. We here obtain a degenerate 2-labelling of G by e.g. assigning label 1 to uv 1 , and label 2 to all other edges. Note that we indeed get σ(u) = 7, σ(v 1 ) = 5, and σ(v 2 ) = σ(v 3 ) = σ(v 4 ) = 6 by this labelling.

-

|E(G[{v 1 , v 2 , v 3 , v 4 }])| = 3.
Suppose, w.l.o.g., that we have the edges v 1 v 2 , v 2 v 3 , and v 3 v 4 . Then v 1 and v 4 are each incident to a unique edge not going to a vertex in {u,

v 1 , v 2 , v 3 , v 4 }. We start from a degenerate 2-labelling of G -{uv 1 , uv 2 , uv 3 , uv 4 , v 1 v 2 , v 2 v 3 , v 3 v 4 },
which exists by minimality of G. We start extending this labelling by assigning label 2 to all uv i 's, so that σ(u) = 8. Then we assign label 2 to v 1 v 2 and v 3 v 4 , and assign either label 1 or label 2 to v 2 v 3 so that σ(v 1 ) ≠ σ(v 2 ). As a result σ(v 1 ), σ(v 2 ), σ(v 3 ), σ(v 4 ) < σ(u), and, because σ(v 1 ) ≠ σ(v 2 ), there cannot be any x-cycle containing any two vertices in {u, v 1 , v 2 , v 3 , v 4 }. Then, the resulting 2-labelling of G is degenerate.

-

|E(G[{v 1 , v 2 , v 3 , v 4 }])| = 2.
There are two possible cases to consider, depending on whether the two edges of G[{v 1 , v 2 , v 3 , v 4 }] are adjacent or not. * If, say, v 1 v 2 and v 2 v 3 are edges, then consider a degenerate 2-labelling of

H = G -{uv 1 , uv 2 , uv 3 , uv 4 , v 1 v 2 , v 2 v 3 }.
Note that v 4 is good or bad. In the former case we assign any label in {1, 2} to uv 4 , while we assign a fitting label in {1, 2} to uv 4 in the latter case. We then assign label 2 to uv 1 , uv 2 , and uv 3 . As a result, note that σ(u) ≥ 7, while σ(v 4 ) ≤ 6; thus, no matter how we label the remaining edges, v 4 cannot be contained in an x-cycle.

Similarly, u cannot eventually be contained in an x-cycle with any of v 1 , v 2 , and v 3 , since their sums will be at most 6. Then we assign any label in {1, 2} to v 1 v 2 , and a label in {1, 2} to v 2 v 3 chosen so that σ(v 1 ) ≠ σ(v 2 ). This makes it impossible to have any two vertices in {u, v 1 , v

σ(v 1 ) ≠ σ(v ′ 1 ) and σ(v 4 ) ≠ σ(v ′ 4
). This makes it impossible to have xcycles in G containing any two vertices in {u, v 1 , v 2 , v 3 , v 4 }, and the resulting 2-labelling is thus degenerate.

-|E(G[{v 1 , v 2 , v 3 , v 4 }])| = 1.
Assume, w.l.o.g., that v 1 v 2 is an edge. Then v 3 and v 4 are both either good or bad. We start from a degenerate 2-labelling of G -{uv 1 , uv 2 , uv 3 , uv 4 , v 1 v 2 }. * Suppose one of v 3 and v 4 is good, say v 3 is good. Assign label 2 to uv 1 , uv 2 , and uv 3 . As a result, we will necessarily get σ(u) > 6, which makes it impossible to eventually have an x-cycle containing u. Then, assign to uv 4 either a fitting label in {1, 2} (if v 4 is bad), or any label (otherwise). In both cases, note that this guarantees v 4 cannot be contained in an x-cycle. Now, denoting by v ′ 1 the neighbour of v 1 not in {u, v 2 }, assign a label in {1, 2} to v 1 v 2 chosen so that σ(v 1 ) ≠ σ(v ′ 1 ). Again, this makes it impossible for v 1 to be contained in an x-cycle, and, thus, similarly for v 2 . Then the resulting 2-labelling of G is degenerate. * Suppose now both v 3 and v 4 are bad. Start by assigning a fitting label in {1, 2} to both uv 3 and uv 4 . Again, this guarantees v 3 and v 4 cannot be contained in an x-cycle, whatever later label choices we make. Now, assuming we currently have σ(v 1 ) ≥ σ(v 2 ), assign label 2 to uv 1 , label 1 to uv 2 , and any label to v 1 v 2 . This guarantees σ(v 1 ) > σ(v 2 ) by the final labelling, which makes it impossible for v 1 , v 2 , and u to belong to an x-cycle. Thus, the resulting extension is degenerate.

-|E(G[{v 1 , v 2 , v 3 , v 4 }])| = 0.
In this case, {v 1 , v 2 , v 3 , v 4 } is an independent set, and we can deal with it in the exact same way we dealt with the last case of Configuration C2.

• Configuration C6.

Assume G contains a 4-vertex u with two 3-neighbours v 1 and v 2 , where v 1 and v 2 share a common 3-neighbour w. We consider several cases, depending on the additional edges in G[{u, v 1 , v 2 , w}], i.e., besides uv 1 , uv 2 , v 1 w, and v 2 w.

-G[{u, v 1 , v 2 , w}] contains exactly two additional edges. We here have both v 1 v 2 and uw in G. We consider a degenerate 2-labelling ℓ of H = G -{uv 1 , uv 2 , uw, v 1 v 2 , v 1 w, v 2 w}, which exists by minimality of G. We extend ℓ to G by assigning label 1 to v 2 w and label 2 to the other five edges.

As a result, we have σ(u) ≥ 7, σ(v 1 ) = 6, and σ(v 2 ) = σ(w) = 5. Also, note that u has degree 1 in H. For these reasons, observe that we have reached a degenerate 2-labelling of G.

-G[{u, v 1 , v 2 , w}] contains exactly one additional edge. There are, here, two cases to consider. * uw is an edge of G, while v 1 v 2 is not. We consider the subgraph H = G -{uv 1 , uv 2 , uw, v 1 w, v 2 w}, which admits a degenerate 2-labelling (due the minimality of G) we wish to extend to G. Note that, here, u, v 1 , and v 2 all have degree 1 in H. We start by assigning label 2 to uv 1 , uv 2 , and uw so that, eventually, σ(u) ≥ 7, and u, however we label the other edges, cannot be contained in an x-cycle. We then assign label 1 to v 1 w, and assign a label in {1, 2} to v 2 w chosen so that σ(w) ≠ σ(v 1 ). This makes it impossible for v 1 , v 2 , and w to be contained in an x-cycle. Then, the resulting 2-labelling of G is degenerate. * v 1 v 2 is an edge of G, while uw is not. We consider the subgraph H = G -{uv 1 , uv 2 , v 1 v 2 , v 1 w, v 2 w}, and a degenerate 2-labelling ℓ of H which exists by minimality of G. Here, note that u has degree 2 in H, while w has degree 1 in H. We try to extend ℓ to G by assigning label 2 to uv 1 , uv 2 , and v 1 v 2 , and label 1 to v 1 w and v 2 w. As a result, σ(u) ≥ 6, σ(v 1 ) = σ(v 2 ) = 5, and σ(w) ≤ 4. If this extension is degenerate, then we are done. Otherwise, note that it must be because u belongs to an x-cycle with its two neighbours in H. We here change to 1 the label assigned to uv 1 . As a result, σ(u) ≥ 5, σ(v 1 ) = 4, σ(v 2 ) = 5, and we still have σ(w) ≤ 4. Also, the sum of u is not the same as that of its two neighbours other than v 1 and v 2 . For these reasons, we have attained a degenerate 2-labelling of G.

-G[{u, v 1 , v 2 , w}] contains no additional edge. We consider a degenerate 2-labelling ℓ of H = G -{uv 1 , uv 2 , v 1 w, v 2 w}, which exists by minimality of G. Let u 1 and u 2 denote the two neighbours of u in H, v ′ 1 denote the unique neighbour of v 1 in H, v ′ 2 denote the unique neighbour of v 2 in H, and w ′ denote the unique neighbour of w in H. We start extending ℓ to G by first assigning labels in {1, 2} to uv 1 and uv 2 chosen so that no two vertices in {u 1 , u 2 , v ′ 1 , v ′ 2 , w ′ } both have the same sum as the resulting σ(u). Note that this is possible, since, upon 2-labelling uv 1 and uv 2 , we can alter σ(u) in three possible ways (while |{u 1 , u 2 , v ′ 1 , v ′ 2 , w ′ }| = 5, so there are at most two values to avoid). This means that, when extending the resulting labelling to v 1 w and v 2 w, the only x-cycle that might contain u is uv 1 wv 2 u. Now, similarly, we 2-label v 1 w and v 2 w so that no two vertices in {v ′ 1 , v ′ 2 , w ′ } both have the same sum as the resulting σ(w), and σ(w) ≠ σ(u). This is possible, since, upon 2-labelling v 1 w and v 2 w, we can alter σ(w) in three possible ways, while at most two values must be avoided. As a result, u cannot belong to an x-cycle together with u 1 ,

u 2 , v ′ 1 , v ′ 2
, and w ′ , while, similarly, w cannot belong to an x-cycle together with v ′ 1 , v ′ 2 , and w ′ . Since also σ(w) ≠ σ(u), we have that uv 1 wv 2 u is not an x-cycle. By these arguments, the resulting 2-labelling of G is thus degenerate.

• Configuration C7.

Assume G contains a 4-vertex u with three 3-neighbours v 1 , v 2 , and v 3 , and that, say, v 1 is also adjacent to two 3-vertices w 1 and w 2 . We consider several cases, depending on the structure of G[{u, v 1 , v 2 , v 3 , w 1 , w 2 }]. Particularly, note that this subgraph can have several edges, and also that some vertices in {u, v 1 , v 2 , v 3 , w 1 , w 2 } can actually be the same (identified). Actually, since G is simple, note that no three vertices in {u, v 1 , v 2 , v 3 , w 1 , w 2 } can be the same, so we only need to consider pairs of identified vertices. Precisely, some of the w i 's can actually be some of the v i 's (v 2 and v 3 ); so, there are at most two pairs of identified vertices. We first treat the cases where there are two pairs of identified vertices, then one pair, and finally the case where there are no identified vertices. In each case, we treat subcases depending on the number of edges incident to two vertices of {u, v 1 , v 2 , v 3 , w 1 , w 2 }.

-Assume that {u, v 1 , v 2 , v 3 , w 1 , w 2 } contains exactly two pairs of identified vertices. Then we actually have, say, w 1 = v 2 and w 2 = v 3 . Note that we cannot have the edge v 2 v 3 in G by Configuration C6. We here consider a degenerate 2labelling of G -{uv 1 , uv 2 , uv 3 , v 1 v 2 , v 1 v 3 } (which exists by minimality of G), and extend it to G as follows. We first assign label 2 to uv 1 , uv 2 , and uv 3 , as well as label 1 to v 1 v 2 . This guarantees σ(u) ≥ 7, and thus u cannot be contained in an x-cycle. Last, we assign a label in {1, 2} to v 1 v 3 chosen so that σ(v 1 ) ≠ σ(v 2 ). Note that this guarantees v 1 , and thus similarly v 2 and v 3 , cannot belong to an x-cycle. Thus, the resulting 2-labelling of G is degenerate.

-Assume now {u, v 1 , v 2 , v 3 , w 1 , w 2 } contains only one pair of identified vertices. W.l.o.g., we may assume w 2 = v 2 . By Configuration C6, we may suppose w 1 v 2 and w 1 v 3 are not edges of G, and similarly for v 2 v 3 . Also, v 1 v 3 is not an edge (since

w 1 ≠ v 3 ). Consider a degenerate 2-labelling of G -{uv 1 , uv 2 , uv 3 , v 1 w 1 , v 1 v 2 },
, uv 2 , v 1 v 2 }, then note that C = N * (V (W )
) is a frontier for W , and that |E(V (W ), C)| = 4. Since, upon 2-labelling the edges of W , we can alter σ(u) in three possible ways, there is a way to 2-label the edges of W so that u is not contained in any x-cycle not contained in W (recall Lemma 4.4(1)). Thus, when doing so, if the attained 2-labelling of G is not degenerate, then it must be because of the σ(u)-cycle uv 1 v 2 u contained in W . In this case, by changing the label assigned to v 1 v 2 , we then get σ(u) ≠ σ(v 1 ) = σ(v 2 ), while only the sums of v 1 and v 2 were altered. Thus, here, we have reached a degenerate 2-labelling of G. * Assume now w 1 is good. Start by assigning label 1 to v 1 w 1 and v 1 v 2 , label 2 to uv 1 and uv 2 , and either a fitting label in {1, 2} to uv 3 (if v 3 is bad), or any label in {1, 2} to uv 3 (otherwise). As a result, we get σ(u) ≥ 6, σ(v 1 ) = 4, and σ(v 2 ) ≤ 5. Also, it can be noted that we necessarily have σ(u) > σ(v 3 ), since, to have σ(u) ≤ σ(v 3 ), we must have σ(u) = σ(v 3 ) = 6, which requires uv 3 to be assigned label 2, which would guarantee σ(u) > 6.

These arguments guarantee u cannot be contained in any x-cycle. So if an x-cycle exists, then it must contain w 1 , v 1 , and v 2 , in which case σ(w 1 ) = σ(v 1 ) = σ(v 2 ) = 4. Then, by changing to 2 the label assigned to v 1 v 2 , we obtain a degenerate 2-labelling of G. Particularly, in that case, we get σ(v 1 ) = σ(v 2 ) = 5 and σ(w 1 ) = 4, while we still have σ(u) ≥ 6, and thus we preserve that there is no x-cycle containing u.

-From now on, we may thus assume no two vertices in {u, v 1 , v 2 , v 3 , w 1 , w 2 } are the same. We now distinguish a few cases, depending on the number of additional edges that

H = G[{u, v 1 , v 2 , v 3 , w 1 , w 2
}] possesses (i.e., besides the edges uv 1 , uv 2 , uv 3 , v 1 w , and v 1 w 2 ). Note that these possible additional edges are uw 1 , As mentioned earlier, there are two main possible cases.

uw 2 , v 2 v 3 , v 2 w 1 , v 2 w 2 , v 3 w 1 , v 3 w 2 ,
• H contains uw 1 and v 2 v 3 .

In this case, we consider G -{uv 1 , uv 2 , uv 3 , uw 1 , v 1 w 1 , v 2 v 3 }, which admits a degenerate 2-labelling by minimality of G. We extend this labelling to G as follows. First we assign label 2 to uv 1 , uv 2 , uv 3 , and uw 1 so that σ(u) = 8 and u cannot be involved in an x-cycle, however we label the other edges. Then we assign a label in {1, 2} to v 1 w 1 chosen so that the resulting σ(v 1 ) is different from σ(w 2 ). Note that this guarantees that v 1 , and thus w 1 , cannot be contained in x-cycles. Last, denoting by v ′ 2 the neighbour of v 2 not in {u, v 3 }, we assign a label in

{1, 2} to v 2 v 3 chosen so that the resulting σ(v 2 ) is different from σ(v ′
2 ). This guarantees v 2 and v 3 are not contained in x-cycles. The resulting 2-labelling of G is then degenerate.

• H contains w 1 w 2 and v 2 v 3 . Start from a degenerate 2-labelling of G -{uv 1 , uv 2 , uv 3 , v 1 w 1 , v 1 w 2 , w 1 w 2 , v 2 v 3 }
, which exists by minimality of G. We extend this labelling to G in the following manner. First assign label 2 to uv 1 , uv 2 , and uv 3 , so that σ(u) ≥ 7 and u cannot be contained in an x-cycle, however the other edges are 2-labelled. Then assign any label in {1, 2} to w 1 w 2 , and assign labels to v 1 w 1 and v 1 w 2 chosen so that σ(w 1 ) ≠ σ(w 2 ). Note that this guarantees w 1 and w 2 , and thus v 1 , cannot be contained in

x-cycles. Last, denoting by v ′ 2 the neighbour of v 2 not in {u, v 3 }, assign a label in {1, 2} to v 2 v 3 so that the resulting σ(v 2 ) is different from σ(v ′
2 ). Similarly, this guarantees v 2 , and thus v 3 , cannot be contained in an x-cycle. Then the resulting 2-labelling of G is degenerate. * H contains no additional edge.

Consider a degenerate 2-labelling of G -{uv 1 , uv 2 , uv 3 , v 1 w 1 , v 1 w 2 }, which exists by minimality of G. We extend this labelling to G as follows. First assign either a fitting label in {1, 2} to v 1 w 1 (if w 1 is bad), or any label in {1, 2} to v 1 w 1 (otherwise, if w 1 is good). Then assign to v 1 w 2 either a fitting label in {1, 2} if w 2 is bad, if w 2 is good, a label in {1, 2} chosen so that the resulting σ(w 2 ) is different from σ(w 1 ). This guarantees that w 1 and w 2 cannot both be contained in an x-cycle upon labelling the other edges. Particularly, if, later on, v 1 belongs to some x-cycle, then that xcycle must also contain u. Now, for each uv i with i ∈ {2, 3} such that v i is bad, assign a fitting label in {1, 2} to uv i . This guarantees v i cannot be contained in an x-cycle. If none of v 2 and v 3 were good, then, by assigning a label in {1, 2} to uv 1 chosen so that σ(u) is different from the sum of the unique neighbour of u not in {v 1 , v 2 , v 3 }, we obtain a degenerate 2labelling of G. Otherwise, if v 2 and/or v 3 were/was good, then there remain two or three edges (including uv 1 ) to be labelled. Let W be the induced subgraph of G containing exactly these two or three edges, and note that Up to symmetry, there are three main possible cases.

C = N * (V (W ))∖{v i ∶ v i ∈ {v 2 , v 3 } and v i was bad} is a frontier for W , with |E(V (W ), C)| = 1 + 2|E(W )|,
• H contains w 1 w 2 . Consider a degenerate 2-labelling of G -{uv 1 , uv 2 , uv 3 , v 1 w 1 , v 1 w 2 , w 1 w 2 }, which exists by minimality of G. We extend it to one of G as follows. Assuming σ(w 1 ) ≥ σ(w 2 ), start by assigning label 2 to v 1 w 1 and label 1 to v 1 w 2 and w 1 w 2 . Then we get σ(w 1 ) > σ(w 2 ), and, however the other edges are 2-labelled, this makes it impossible for w 1 and w 2 to both belong to an x-cycle. We thus get ourselves in a situation similar to one we ran into in the previous case (particularly, every eventual x-cycle must contain u), and we can deal with it in the exact same way (by 2-labelling the uv i 's) to obtain a degenerate 2-labelling of G.

• H contains uw 1 . Consider a degenerate 2-labelling of G -{uv 1 , uv 2 , uv 3 , uw 1 , v 1 w 1 , v 1 w 2 }
, which exists by minimality of G. We extend this degenerate 2-labelling to one of G in the following way. • If, say, v 2 is good, then we assign label 2 to uv 1 , uv 2 , and uw 1 , and either a fitting label in {1, 2} to uv 3 (if v 3 is bad), or any label in {1, 2} to uv 3 (otherwise). As a result, σ(u) ≥ 7, which makes it impossible, from here, to have u contained in x-cycles. Likewise, v 2 and v 3 cannot be contained in x-cycles, due to how we labelled uv 2 and uv 3 . Now, assign either a fitting label in {1, 2} to v 1 w 2 (if w 2 is bad), or any label in {1, 2} to v 1 w 2 (otherwise), and, finally, assign a label in {1, 2} to v 1 w 1 chosen so that σ(w 1 ) ≠ σ(w 2 ). All these choices guarantee that w 1 and w 2 , and similarly v 1 , cannot be contained in x-cycles. Then the resulting 2-labelling of G is degenerate. • Now assume both v 2 and v 3 are bad. Start by assigning a fitting label in {1, 2} to uv 2 and uv 3 so that v 2 and v 3 , eventually, cannot be contained in x-cycles. Next, assign either a fitting label to v 1 w 2 (if w 2 is bad), or any label to v 1 w 2 (otherwise). Then, assign any labels in {1, 2} to v 1 w 1 and uv 1 , and eventually label uw 1 so that σ(v 1 ) ≠ σ(w 1 ). It can be checked that this guarantees v 1 , and thus u, w 1 , and w 2 , cannot be contained in x-cycles. Then, we get a degenerate 2-labelling of G. and w 2 different from v 1 . Then, again, we have our conclusion. For each i ∈ {1, 2}, let thus ℓ i be a 2-labelling of uv 1 , v 1 w 1 , and v 1 w 2 that guarantees, when combining ℓ and ℓ i to a 2-labelling ℓ ′ i , that ℓ ′ i (uv 1 ) = i and v 1 is not part of an x-cycle (together with w 1 and w 2 ). Let now u ′ denote the unique neighbour of u not in {v 1 , v 2 , v 3 }, and, for every i ∈ {2, 3}, let v ′ i denote the unique neighbour of v i not in {u, v 2 , v 3 }. We consider two last cases:

• H contains v 2 v 3 . Start from a degenerate 2-labelling ℓ of G -{uv 1 , uv 2 , uv 3 , v 1 w 1 , v 1 w 2 , v 2 v 3 },
• If, say, σ ℓ ′ 2 (v 2 ) > σ ℓ ′ 2 (v 3 ) (that is, ℓ(v 2 v ′ 2 ) = 2 > 1 = ℓ(v 3 v ′ 3
)), then note that, when extending ℓ ′ 2 to G by assigning label 2 to uv 2 , uv 3 , and v 2 v 3 , we obtain a 2-labelling of G where σ(u) ≥ 7, and, thus, by which u cannot be contained in an x-cycle at all (in particular, with v 1 ). Also, since we get σ(v 2 ) > σ(v 3 ), both v 2 and v 3 cannot belong to x-cycles. Altogether, the resulting 2-labelling of G is thus degenerate.

• Now, if ℓ(v 2 v ′ 2 ) = ℓ(v 3 v ′ 3 )
, then, starting from ℓ ′ 2 , assign label 1 to uv 2 and v 2 v 3 , and label 2 to uv 3 . As a result, σ(v 2 ) < σ(v 3 ) ≤ 5, while σ(u) ≥ 6. If an x-cycle appears, then it must contain u, u ′ , and v 1 , and this occurs only if

σ(u) = σ ℓ ′ 2 (u ′ ) = σ ℓ (u ′ ) = σ ℓ ′ 2 (v 1 ) = 6
, meaning that ℓ(uu ′ ) = 1. In that case, start over but with extending ℓ ′ 1 instead, assigning label 1 to uv 2 and v 2 v 3 , and label 2 to uv 3 . As a result, we still have σ(u ′ ) = 6, while σ(u) = 5. If an x-cycle exists, then it must include u, v 1 , and v 3 , which can only occur if ℓ(v 2 v ′ 2 ) = ℓ(v 3 v ′ 3 ) = 2 (as otherwise we would have σ(v 2 ), σ(v 3 ) ≤ 4), and σ(v ′

3 ) = 5. We can deduce also that σ(v ′ 2 ) = 5, upon swapping the labels of uv 2 and uv 3 . So, now, just start again from ℓ ′ 2 , and assign label 2 to all of uv 2 , uv 3 , and v 2 v 3 . As a result, σ(u

′ ) = 6, σ(u) = 7, σ(v 1 ) = σ(v 2 ) = σ(v 3 ) = 6,
d 3 ≤ 2d 1 + 1)
, while u is supposed to be a 6 + -vertex. By Configuration C1, recall also that G cannot have an edge joining two v i 's, nor an edge joining some v i and some w j . However, G might have edges joining some of the w i 's, which means that H is not necessarily an induced subgraph of G. In any case, H admits a degenerate 2-labelling ℓ by minimality of G, which we wish to extend to G.

As a first step, we perform the following. Note that G[{w 1 , . . . , w d 2 }] has maximum degree at most 2, meaning that each of its connected components is either an isolated vertex, a non-empty path, or a cycle. We consider each C of these connected components in turn, choose any arbitrary one w i of its vertices, and, for every w j ∈ V (C) ∖ {w i }, assign label 1 to uw j . Once this is achieved, in every connected component of G[{w 1 , . . . , w d 2 }] there is thus exactly one w i which is incident to an unlabelled edge, going to u, by the resulting labelling. For these reasons, and because ℓ is degenerate, there cannot be any x-cycle at this point. Now consider every remaining unlabelled edge uw i (if any) in turn. Note that, now, w i must be a good or a bad 3-vertex. If w i is bad, then we assign a fitting label in {1, 2} to uw i , while we assign, say, label 1 to uw i otherwise, if w i is good. Let now W denote the subgraph G[{uv 1 , . . . , uv d 1 }] (which might be empty, if d 1 = 0). Note that W is an induced subgraph of G. Also, the resulting labelling ℓ ′ we have built from ℓ up to this point (possibly ℓ ′ = ℓ) is actually a 2-labelling of G ∖ e W . Again, by Observation 4.3, because k ≥ 6, note that, by how we assigned labels to the uw i 's, there cannot be any x-cycle by ℓ ′ . Thus, to be done, it remains to label the uv i 's, if any. Still by Observation 4.3, we only need to make sure u is not involved in a σ(u)-cycle, thus involving two of the x i 's (since a 6 + -vertex, by a 2-labelling, cannot have the same sum as an adjacent 3 --vertex). By all the previous arguments, it can be noted that C = {x 1 , . . . , x d 3 } forms a frontier for W with |C| = d 3 . Upon 2-labelling the uv i 's, note that σ(u) can be altered in d 1 + 1 way, by any amount in {d 1 , . . . , 2d 1 }. Since d 3 ≤ 2d 1 + 1, by Lemma 4.4(2) there is a degenerate extension of ℓ ′ to G.

As a final remark, note that if d 1 = 0, then d 3 ≤ 1, and thus there is at most one x i , which makes it impossible for u to ever be contained in any x-cycle by a 2-labelling.

Thus, we reach a contradiction if G contains any of the configurations. ◇ Back to the proof of Theorem 4.1, we define V 1 as the set of all 3 + -vertices of G, and V 2 as the set of all its 2 --vertices. We consider the charge function ω where ω(v) = d(v) -10 G, and they are incident to at most two edges, assigned label 2, going to 4-vertices.

• If H is a tree, then we assign label 2 to all its edges. As a result, note that all vertices of H have sum at most 6, while these vertices do not form cycles. Also, every vertex in V (G) ∖ V (H) having a neighbour in H is a 4-vertex, thus with sum 8. From this, we deduce that the vertices of H cannot be contained in some x-cycle.

• Assume now H contains cycles. Recall that H is 2-degenerate; we consider two cases:

-Assume first H contains a 1-vertex v, i.e., d H (v) = 1. This means v is incident to exactly two edges going to 4-vertices of G, which edges are assigned label 2 by ℓ. We can here extend ℓ to the edges of H the exact same way we proved the similar case in the proof of Theorem 3.2. That is, we can 2-label H so that, modulo 2, the resulting sums form a degenerate 2-colouring (even when taking into account the labels assigned to the incident edges going to the 4-vertices of G) of H, except maybe because of v. Since v is not contained in any cycle of H, and σ(v) ≤ 6, no x-cycle exists.

-Assume now H has minimum degree 2, and let v be a 2-vertex of H, i.e., d H (v) = 2. Thus, v is incident to one edge (assigned label 2) going to a 4-vertex of G, and v is adjacent to two vertices v 1 and v 2 in H. Similarly as in the proof of Theorem 3.2, we can 2-label H so that the resulting sums, modulo 2, and even when taking into account the contribution of the labels assigned to the edges incident to the 4-vertices of G, form a degenerate 2-colouring of H, except maybe because of v. If v has the desired sum modulo 2, then we are done. Otherwise, we can again assume that σ(v) = σ(v 1 ) = σ(v 2 ), and that the three sums are odd. Thus, σ(v) = 5, and, w.l.o.g., ℓ(vv 1 ) = 1 and ℓ(vv 2 ) = 2. For x = 5, if no x-cycle contains v, then we are done. So, we can assume v is contained in an x-cycle for x = 5. If we are not done when changing ℓ(vv 2 ) to 1, then it means that v 2 has degree 3 in H, and that its two neighbours other than v have sum 4 (as the only possibly x-cycle now must verify x = 4 and contain v 2 and its two neighbours other than v). This contradicts the fact that, for x = 5, H contained an x-cycle in the first place.

Thus, in every case, we end up with a degenerate 2-labelling of G at some point.

Questions and problems involving Conjecture 2.1

In this concluding section, we survey a few open questions and problems connecting to Conjecture 2.1 in a more or less obvious way, giving yet more significance to this conjecture.

The importance of label 3 for the 1-2-3 Conjecture

As showcased by several known results, the 1-2-3 Conjecture, if true (which might be the case, see [START_REF] Keusch | A Solution to the 1-2-3 Conjecture[END_REF]), would be tight; notably, there exist infinitely many graphs G with various structures that verify χ Σ (G) = 3. A natural question to wonder, is how tight the 1-2-3 Conjecture would be in general, or, put differently, whether there exist graphs for which the use of label 3 is "very crucial" in designing proper 3-labellings. This leads to several side questions of interest, some of which have already been investigated in the literature. For instance, let us mention [START_REF] Bensmail | On the Role of 3s for the 1-2-3 Conjecture[END_REF], in which the authors investigate the existence of graphs needing lots of 3's in their proper 3-labellings, and [START_REF] Bensmail | On Proper Labellings of Graphs with Minimum Label Sum[END_REF], in which the authors strive to design proper 3-labellings minimising the sum of assigned labels. Regarding these investigations in [START_REF] Bensmail | On the Role of 3s for the 1-2-3 Conjecture[END_REF][START_REF] Bensmail | On Proper Labellings of Graphs with Minimum Label Sum[END_REF], note that Conjecture 2.1, if true, could provide new results, such as new bounds on some parameters.

In some sense, Conjecture 2.1 lies in that line of research, as the conjecture is precisely about the structure of the sum conflicts one can hope for by a 2-labelling that is "almost proper", thus when label 3 is put aside. To make it more precise, let us introduce the following terminology. For a graph G, any labelling ℓ of G, and any x ≥ 1, we define the xsubgraph of G (by ℓ) as the subgraph induced by the vertices v with σ(v) = x. So, the 1-2-3 Conjecture, put differently, states that every nice graph should admit a 3-labelling where the x-subgraph is empty for every x. Conjecture 2.1, now, states that, when considering 2-labellings, every graph should admit a 2-labelling where all x-subgraphs are forests.

Playing with this way of seeing things, one can come up with weaker and stronger versions of Conjecture 2.1, which might be worth considering. Regarding weaker versions of the conjecture, one first step towards Conjecture 2.1 could be to wonder whether all graphs admit 2-labellings where all x-subgraphs might e.g. contain a limited number of cycles, be bipartite, etc., or, more generally speaking, any type of structure weaker than a forest. Regarding stronger versions of Conjecture 2.1, one could ask the x-subgraphs to be more than forests, such as restricted forests (e.g. star forests, linear forests, etc.). Note that some of the results we have provided in the current work already make a step in that direction, as e.g. our proof of Theorem 3.1 actually yields that every connected bipartite graph admits a 2-labelling where all x-subgraphs are star forests. Even stronger, there is at most one x where the x-subgraph is not empty, while, if this x exists, the x-subgraph consists of one star and isolated vertices. By exploiting the structure of bipartite graphs G with χ Σ (G) = 3, which was well identified in [START_REF] Thomassen | The 3-flow conjecture, factors modulo k, and the 1-2-3-conjecture[END_REF], it is even possible to go beyond this result, by designing, for every bipartite graph, 2-labellings where the x-subgraphs are star forests with bounded degree (refer e.g. to [START_REF] Bensmail | On Proper Labellings of Graphs with Minimum Label Sum[END_REF] for an illustration of how this can be done).

Such concerns, again, connect to previous investigations on the topic; in particular, they connect to the so-called 1-2 Conjecture raised by Przybyło and Woźniak in [START_REF] Przybyło | On a 1,2 Conjecture[END_REF]. In short, the 1-2 Conjecture is a total version of the 1-2-3 Conjecture where also vertices get labelled, the label assigned to any vertex taking part to its sum, and only labels 1 and 2 can be assigned. Rephrased differently, because we are considering labellings assigning strictly positive labels only, the 1-2 Conjecture asks whether, for every graph G, its corona product G ⊙ K 1 , where every vertex of G gets attached a pendant vertex, verifies χ Σ (G ⊙ K 1 ) ≤ 2. Maybe one way to get progress towards the 1-2 Conjecture could be to prove that, indeed, all graphs admit 2-labellings where all x-subgraphs are bipartite, since, in the total version of the problem, bipartite graphs are very easy to deal with (see e.g. [START_REF] Przybyło | On a 1,2 Conjecture[END_REF]).

A related interesting question we have regarding those concerns is about the existence of graphs such that, in all their proper 3-labellings, there must be at least two adjacent edges being assigned label 3. As far as we are aware, no such graphs are known to date, although graphs requiring "lots" of 3's do exist (see [START_REF] Bensmail | On the Role of 3s for the 1-2-3 Conjecture[END_REF]). The existence of such graphs would imply that, in some circumstances, labels 1 and 2 only are far from sufficient, as there are local "hard" places where multiple 3's must be placed to get a proper 3-labelling.

Progressing towards Conjecture 2.1

Regarding Conjecture 2.1 and the results provided in the current work, the most natural next steps to make could concern other classes of graphs with vertex-arboricity at most 2. For instance, as mentioned earlier, graphs with maximum degree 4 and graphs with degeneracy 3 have vertex-arboricity at most 2, and proving Conjecture 2.1 for these graphs would be a nice strengthening over some of the main results provided in this work. Note, in particular, that the last arguments we employed by the end of the proof of Theorem 4.7 could be used for graphs with maximum degree 4 in which the set of all degree-4 vertices is independent. Regarding Theorem 4.1, a natural question would of course be about generalisations to denser graphs, i.e., with larger maximum average degree. Due to Corollary 4.6, one could specifically wonder about triangle-free planar graphs.

On a different note, we also believe it could be crucial to come up with a more general version of Lemma 4.4, which would cover all possible ways for x-cycles to appear when extending 2-degenerate labellings.

Generalising the 1-2-3 Conjecture to the dichromatic number

Our original motivations behind our investigations in the current work stem from different questions, that have to do with generalisations of the 1-2-3 Conjecture to digraphs. Note that generalising the 1-2-3 Conjecture to digraphs is not an obvious task, as there exist multiple notions of proper colouring in digraphs, and also, by a labelling of the arcs of a digraph, for every vertex there are multiple ways to regard its associated sum.

In a recent work [START_REF] Bensmail | Adding Direction Constraints to the 1-2-3 Conjecture[END_REF] (in which several other known generalisations are surveyed), we considered a variant where, for any oriented graph #» G, the goal is to determine χ #» Σ ( #» G), which is defined as the least k ≥ 1 such that #» G admits a k-labelling where the resulting sum function σ (computed as in the underlying graph G) forms an oriented colouring of #» G (which, recall, means that for every two colour classes α and β, all arcs joining a vertex with colour α and one with colour β go the same direction, i.e., from the latter to the former, or vice versa). The next step we considered making, was to consider the same problem, but restricted to dicolourings (introduced in [START_REF] Neumann-Lara | The dichromatic number of a digraph[END_REF]), which are another classical way to generalise proper colourings to digraphs. Recall that a dicolouring of a digraph is a colouring where no colour class induces a directed cycle, and that the dichromatic number of a digraph is the least k ≥ 1 in a k-dicolouring. Similarly as in [START_REF] Bensmail | Adding Direction Constraints to the 1-2-3 Conjecture[END_REF], we would then have defined e.g. an acyclic labelling of a digraph D as a labelling where σ is a dicolouring of D, and defined #» χ Σ (D) as the smallest k ≥ 1 such that acyclic k-labellings of D exist.

One problem we encountered, however, is that if #» G is an orientation of a graph G, then clearly #» χ Σ ( #» G) ≤ χ d Σ (G) (a problem we did not have in the variant considered in [START_REF] Bensmail | Adding Direction Constraints to the 1-2-3 Conjecture[END_REF], since χ Σ (G) ≤ χ #» Σ ( #» G) there). Since χ d Σ (G) ≤ 3 holds for every graph G, recall [START_REF] Gao | A Relaxed Case on 1-2-3 Conjecture[END_REF], this means #» χ Σ ( #» G) is always small (at least for #» G being an oriented graph), and things all mostly fall down to proving or disproving Conjecture 2.1. Thus, investigating the parameter #» χ Σ can be seen as a step towards understanding the parameter χ d Σ and Conjecture 2.1. In particular, one can consider proving that #» χ Σ ( #» G) ≤ 2 holds when #» G has particular properties.

  since every vertex of C, by definition, has at least one neighbour in W , then |E(V (W ), C)| ≥ n + 2m, and thus |C| ≤ |E(V (W ), C)| -m. Altogether, we thus deduce that n

Claim 4 . 5 .

 45 G does not contain any of the following configurations: (C1) a 2 --vertex adjacent to a 4 --vertex; (C2) a 3-vertex adjacent to three 3-vertices; (C3) a 5-vertex adjacent to two 2 --vertices; (C4) a 5-vertex adjacent to a 2 --vertex and a 3-vertex; (C5) a 4-vertex adjacent to four 3-vertices; (C6) a 4-vertex adjacent to two 3-neighbours sharing a 3-neighbour;

, 1 ≤ |R| ≤ 3 .

 13 Denote by C the set of the neighbours (in G) other than u of the good v i 's. By the definition of a good 3-vertex, note that, upon 2-labelling the edges of R, all eventual x-cycles must contain u. Thus, C forms a frontier for W , and |E(V (W ), C)| = 2|R|. On the other hand, through 2-labelling the edges of R, we can alter σ(u) in |R| + 1 ways (i.e., increment σ(u) by any value in {|R|, . . . , 2|R|}). Thus, by Lemma 4.4(1), there is a way to 2-label the edges of R to get a degenerate 2-labelling of G.• Configuration C3.Assume G contains a 5-vertex u adjacent to two 2 --vertices v 1 and v 2 . Consider W , the subgraph of G with edge set {uv 1 , uv 2 }. By Configuration C1, recall that v 1 and v 2 cannot be adjacent in G; thus, W is an induced subgraph. By minimality of G, there is a degenerate 2-labelling ℓ of G ∖ e W . By Observation 4.3, note that, however ℓ is extended to G (thus to uv 1 and uv 2 ), we cannot have σ(u) ∈ {σ(v 1 ), σ(v 2 )}. Thus, when extending ℓ to a degenerate 2-labelling of G, we only need to make sure u is not involved in a σ(u)-cycle, which cycle would contain two of the three neighbours of u other than v 1 and v 2 . Then, C = N (u) ∖ {v 1 , v 2 } is a frontier for W with |E(V (W ), C)| ≤ 5. By Lemma 4.4(1), we can thus extend ℓ to a degenerate 2-labelling of G, since, upon 2-labelling uv 1 and uv 2 , we can alter σ(u) in three ways.• Configuration C4.Assume G contains a 5-vertex u adjacent to a 2 --vertex v and a 3-vertex w. By Configuration C1, v and w are not adjacent. Consider thus W , the induced subgraph of G with edge set {uv, uw}. By minimality of G, there is a degenerate 2-labelling ℓ of G ∖ e W , which we wish to extend to G. Note that w is good or bad.

  3, we cannot have σ(u) = σ(v) by a 2-labelling of G. Thus, C = N (u) ∖ {v, w} is a frontier for the induced subgraph W ′ containing the only edge that remains to be labelled, uv, and |C| = 3. Since, upon 2-labelling uv, we can alter σ(u) in two ways, by Lemma 4.4[START_REF] Bensmail | Adding Direction Constraints to the 1-2-3 Conjecture[END_REF] we can extend the labelling to a degenerate 2-labelling of G.

  while, upon 2-labelling the edges of W , all resulting x-cycles (if any) must contain u. Since, by 2-labelling the edges of W , we can alter σ(u) in |E(W )| + 1 ways, we deduce, by Lemma 4.4[START_REF] Ahadi | Algorithmic complexity of proper labeling problems[END_REF], that there is a degenerate extension of the 2-labelling to G. * H contains exactly one additional edge.

and σ(v ′ 2 ) = σ(v ′ 3 ) = 5 .

 235 From this, we deduce that we have reached a degenerate 2-labelling of G.• Configuration C8. Assume G contains a k-vertex u with k = d 1 + d 2 + d 3 ≥ 6, where u is adjacent to d 1 2 --vertices v 1 , . . . , v d 1 , to d2 3-vertices w 1 , . . . , w d 2 , and to d 3 4 + -vertices x 1 , . . . , x d 3 , and k ≤ 3d 1 + d 2 + 1. This last condition means that d 3 ≤ 2d 1 + 1. Denote by H the subgraph G -{uv 1 , . . . , uv d 1 , uw 1 , . . . , uw d 2 }. Note that H is a proper subgraph of G (i.e., |E(H)| < |E(G)|), as otherwise we would have d 1 = d 2 = 0 and d 3 ≤ 1 (since

  which admits a degenerate 2-labelling ℓ we wish to extend to G. In this case, note that v 3 is either good or bad; we treat the two possible cases separately. * Assume first that v 3 is bad. Start by assigning a fitting label in {1, 2} to uv 3 .Recall that this means that, however we label the other remaining edges, v 3 cannot be contained in any x-cycle. Also, if u ends up belonging to an x-cycle, then that cycle cannot contain v 3 . Assuming now σ ℓ (v 1 ) ≥ σ ℓ (v 2 ) (that is, if the only edge incident to v 1 in H is assigned label 1 by ℓ, then also the only edge incident to v 2 is assigned label 1), we assign label 2 to uv 1 and v 1 v 2 , and label 1 to uv 2 . As a result, σ(v 1 ) > σ(v 2 ), which makes it impossible for v 1 and v 2 to belong to an x-cycle, and similarly for u, v 1 , and v 2 . Since v 1 and v 2 both have only one neighbour not in {v 1 , v 2 , u} each, we deduce that the resulting 2-labelling of G is degenerate. * Now assume v 3 is good. Start by assigning label 1 to uv 1 , uv 2 , and uv 3 ,

  2 , v 3 , v 4 } belonging to an x-cycle, and the resulting 2-labelling of G is thus degenerate. * If, say, v 1 v 2 and v 3 v 4 are edges, then start from a degenerate 2-labelling of G -{uv 1 , uv 2 , uv 3 , uv 4 , v 1 v 2 , v 3 v 4 }. First, assign label 2 to uv 1 , uv 2 , uv 3 , and uv

[START_REF] Bensmail | On the Role of 3s for the 1-2-3 Conjecture[END_REF]

, so that σ(u) = 8 and, eventually, no x-cycle can contain u. Now assign labels in {1, 2} to v 1 v 2 and v 3 v 4 , chosen so that, assuming v ′ 1 and v ′ 4 denote the neighbour of v 1 and v 4 , respectively, not in {u, v 2 , v 3 }, we get

  which exists by minimality of G. The previous observations imply w 1 and v 3 are good or bad; we extend the degenerate 2-labelling to G as follows. * Assume first w 1 is bad. We start by assigning a fitting label in {1, 2} to v 1 w 1 , so that, however we label the remaining edges, w 1 cannot belong to an x-cycle. Next, we assign to uv 3 either a fitting label in {1, 2} (if v 3 is bad), or any label in {1, 2} (otherwise). Note that this guarantees v 3 is not contained in an x-cycle at this point. A consequence is that, when labelling the other edges, if any x-cycle appears, then it must contain u. It remains to label the edges uv 1 , uv 2 , and v 1 v 2 . If we denote by W the induced subgraph of G with edge set {uv 1

  and w 1 w 2 . Actually, note that we cannot have any of the edges v 2 w 1 , v 2 w 2 , v 3 w 1 , and v 3 w 2 by Configuration C6. So we can only have combinations of edges in {uw 1 , uw 2 , v 2 v 3 , w 1 w 2 }. Note further that if H contains uw 1 , then it cannot also contain uw 2 since u is a 4-vertex and the vertices in {v 1 , v 2 , v 3 , w 1 , w 2 } are pairwise distinct. If H contains uw 1 and w 1 w 2 , then note that G contains Configuration C6, which is a contradiction. Thus, if H contains uw 1 (or, similarly, uw 2 ), then the only other additional edge it can contain is v 2 v 3 ; consequently, if H contains w 1 w 2 , then the only other additional edge it can contain is v 2 v 3 . Particularly, this means H contains at most two additional edges; we treat all possible cases below. * H contains exactly two additional edges.

  which exists by minimality of G. Let us raise a first remark, being that the three edges uv 1 , v 1 w 1 , and v 1 w 2 can be labelled so that none of v 1 , w 1 , and w 2 are contained in x-cycles, and uv 1 is assigned any desired label in {1, 2}. To see this is true, note that if both w 1 and w 2 are bad, then we can assign fitting labels in {1, 2} to v 1 w 1 and v 1 w 2 and then any label in {1, 2} to uv 1 to get the desired conclusion. If, say, w 1 is bad and w 2 is good, then, upon assigning a fitting label in {1, 2} to v 1 w 1 and any label in {1, 2} to v 1 w 2 , we can then assign any label in {1, 2} to uv 1 to get our conclusion. Last, if w 1 and w 2 are both good, then, upon fixing any label in {1, 2} for uv 1 , and then 2-labelling v 1 w 1 and v 1 w 2 , we can have σ(v 1 ) get three possible values, one of which is equal to at most one of the sums of the four neighbours of w 1

Throughout this work, we never refer to a cycle of length x as an x-cycle; every use of the term "x-cycle" always refers to a cycle in which all vertices have sum x by some (possibly partial) labelling.

Note that our goal is not to survey the whole field; we thus refer the interested reader to the references we provide for further information on the topic.

for every vertex v of G. For every vertex v ∈ V 1 we also set ω * (v) = 0, while we setω * (v) = d(v) -10 3 + d V 1 (v) = ω(v) + d V 1 (v) for every v ∈ V 2 . By Configuration C1, for every v ∈ V 2 , note that all neighbours of v lie in V 1 . Thus, d V 1 (v) = d G (v) for every v ∈ V 2 ,and, hence, ω * (v) = -[START_REF] Bensmail | On the Role of 3s for the 1-2-3 Conjecture[END_REF] 3 for every 1-vertex v, while ω * (v) = 2 3 for every 2-vertex v. Below, a 3-vertex is said weak if it is adjacent to exactly one

[START_REF] Bensmail | On the Role of 3s for the 1-2-3 Conjecture[END_REF]-vertex and no 5 + -vertex.

To get a final contradiction to the existence of G, we define a discharging process which, from the initial charge function ω, results in a charge function ω ′ where ω ′ (v) ≥ ω * (v) for every vertex v, from which we can conclude that mad(G) ≥ 10 3 by Theorem 4.2. The rules of our discharging process are the following: (R1) Every 5 + -vertex sends 1 to each of its 2 --neighbours.

(R2) Every 5 + -vertex sends 1 3 to each of its 3-neighbours. (R3) Every 4-vertex sends 1 3 to each of its weak 3-neighbours. (R4) Every 4-vertex sends 1 6 to each of its non-weak 3-neighbours. From now on, we assume that we have applied the discharging process above, Rules R1 to R4, from the initial charge function ω. Let ω ′ (v) denote the resulting charge for every vertex v of G. We now analyse ω ′ (v), w.r.t. d(v) and the neighbourhood of v.

Recall that ω(v) = -7 3 and ω * (v) = -4 3 . By Configuration C1, the unique neighbour of v must be a 5 + -vertex, which sent 1 to v by Rule R1. On the other hand, note that v did not send any charge through Rules R1 to R4. Thus,

Recall that ω(v) = -4 3 and ω * (v) = 2 3 . By Configuration C1, the two neighbours of v must be 5 + -vertices, which both sent 1 to v by Rule R1. On the other hand, note that v did not send any charge through Rules R1 to R4. Thus,

Recall that ω(v) = -1 3 and ω * (v) = 0. By Configuration C1, the three neighbours of v must be 3 + -vertices, and by Configuration C2 at least one of them must be a 4 + -vertex. Note also that v did not send any charge through Rules R1 to R4.

-If v is weak, then v has only one 4 + -neighbour, being a 4-vertex, which sent 1 3 to v by Rule R3. Thus, we have ω

-If v is not weak, then either v is adjacent to at least one 5 + -vertex, or v is adjacent to at least two 4-vertices. In the former case, at least one 5 + -neighbour of v sent 1 3 to v by Rule R2, while, in the latter case, at least two 4-neighbours of v both sent 1 6 to v by Rule 4. Thus, in both cases we have ω

Recall that ω(v) = 2 3 and ω * (v) = 0. By Configuration C1, all neighbours of v must be 3 + -vertices. Note also that v did not receive any charge through Rules R1 to R4.

-If v has weak 3-neighbours, then, by Configuration C7, v has at most two 3-neighbours.

Since v sent 1 3 to each of its weak 3-neighbours by Rule R3, and 1 6 to each of its non-weak 3neighbours by Rule R4, the worst-case scenario is thus when v has two weak 3-neighbours. Thus, we have ω

-Otherwise, if v does not have weak 3-neighbours, then, by Configuration C5, v has at most three non-weak 3-neighbours, to each of which v sent 1 6 by Rule R4. Thus, we have

Recall that ω(v) = 5 3 and ω * (v) = 0. By Configuration C3, v is adjacent to at most one 2 --vertex, to which, if it exists, v sent 1 by Rule R1. Also, by Configuration C4, v cannot be adjacent to both a 2 --vertex and a 3-vertex. And, by Rule R2, v sent 1 3 to each of its 3-neighbours. In all cases, v did not receive any charge through Rules R1 to R4.

-If v is adjacent to a 2 --vertex, then that neighbour is the only vertex that received some charge from v. Thus, we have ω

-Otherwise, only the (at most five) 3-neighbours (if any) of v received some charge from v.

Thus, we have ω

Let us denote by d 1 the number of 2 --neighbours of v, and by d 2 the number of its 3neighbours. By Configuration C8, we have

. Also, recall that ω * (v) = 0. We can suppose that d 1 + d 2 > 0, as otherwise v did not send any charge through Rules R1 to R4, and thus ω ′ (v) = ω(v) > 0 = ω * (v). By Rules R1 and R2, note that v sent 1 to each of its 2 --neighbours and 1 3 to each of its 3-neighbours. Meanwhile, v did not receive any charge through Rules R1 to R4. Thus, we have:

, and thus the same conclusion holds here as well.

Thus, we end up with ω ′ (v) ≥ ω * (v) for every vertex v of G. By Theorem 4.2, we thus deduce that mad(G) ≥ 10 3 , which is a contradiction to our initial hypothesis. So, G cannot exist at all, and the result holds.

Recall that the girth g(G) of a graph G is defined as the length of the shortest cycles of G. It is well known that, in planar graphs, there is a strong connection between the maximum average degree and the girth. Precisely, if G is a planar graph, then mad(G) < 2g(G) g(G)-2 , see e.g. [START_REF] Borodin | On the maximum average degree and the oriented chromatic number of a graph[END_REF]. From this, the authors of [START_REF] Gao | A Relaxed Case on 1-2-3 Conjecture[END_REF] deduced as a side result that Conjecture 2.1 holds for planar graphs with girth at least 6. The same way, from Theorem 4.1 we get:

Through arguments we used to deal with the reducible configurations in the proof of Theorem 4.1, we can also prove Conjecture 2.1 for graphs with maximum edge weight at most 7. Recall that, for some x, y ≥ 1, we say that an edge uv of a graph G is an (x, y)-edge if d(u) = x and d(v) = y. The weight of uv is then defined as x + y, while the maximum edge weight of G is the maximum weight of one of its edges. Proof. The proof is by induction on |V (G)| + |E(G)|, so we can assume G is connected. As a base case, note that if G contains only one edge, thus a (1, 1)-edge, then G is actually K 2 , in which case it suffices to assign label 1 to that edge to obtain a degenerate 1-labelling of G. So, we now focus on the more general case.

By reduction arguments we used to prove Theorem 4.1, note that we can deduce a degenerate 2-labelling of G whenever G contains an (x, y)-edge with (x, y) lying in {(1, 2), [START_REF] Ahadi | Algorithmic complexity of proper labeling problems[END_REF][START_REF] Bensmail | An injective version of the 1-2-3 Conjecture[END_REF], [START_REF] Ahadi | Algorithmic complexity of proper labeling problems[END_REF][START_REF] Bensmail | On the Role of 3s for the 1-2-3 Conjecture[END_REF], (2, 2), (2, 3), (2, 4)} (where we assume x ≤ y). Indeed, if G contains such an (x, y)-edge, then we can remove some edges from G, invoke induction to deduce a degenerate 2-labelling of the remaining graph, and extend it to the whole of G, due to the locally sparse structure. So, in what follows, we can assume G does not contain any such (x, y)-edge.

From this, we are also done whenever G contains a 2-vertex. Indeed, assume G contains a 2-vertex v with neighbours u 1 and u 2 . Since G has maximum edge weight at most 7, then, by the previous arguments, u 1 and u 2 must be 5-vertices. Also, u 1 and u 2 cannot be adjacent, as otherwise G would contain an edge with weight 10. Consider G ′ the graph obtained from G by contracting v (i.e., removing v and adding the edge u 1 u 2 ), and a degenerate 2-labelling ℓ ′ of G ′ , which exists by induction. Note that G ′ is simple since u 1 and u 2 are not adjacent in G. We extend ℓ ′ to a degenerate 2-labelling ℓ of G by setting ℓ(e) = ℓ ′ (e) for every edge e ∈ E(G) ∖ {vu 1 , vu 2 }, and ℓ(vu 1 ) = ℓ(vu 2 ) = ℓ ′ (u 1 u 2 ). As a result, note that σ ℓ (u 1 ) = σ ℓ ′ (u 1 ) and σ ℓ (u 2 ) = σ ℓ ′ (u 2 ). Also, by Observation 4.3, we must have σ ℓ (v) < σ ℓ (u 1 ) and σ ℓ (v) < σ ℓ (u 2 ). Since ℓ ′ is degenerate, it is now easy to see, by the previous arguments, that ℓ is degenerate in G.

We are now also done if G contains any 1-vertex. Indeed, if G contains a 1-vertex v neighbouring another vertex u, then, by the previous arguments, u must be a 5 + -vertex, thus a 5-vertex or a 6-vertex since G has maximum edge weight at most 7. If u is a 6-vertex, then its six neighbours must actually be 1-vertices, meaning that G is a star, and we can just assign label 1 to all its edges to deduce a degenerate 1-labelling. If u is a 5-vertex, then, similarly, since G is here assumed to not contain any 2-vertex, the five neighbours of u must be 1-vertices, and G is a star in which it suffices to assign label 1 to all its edges. Thus, from now on we can assume G has minimum degree at least 3, and, because G has maximum edge weight at most 7, actually we can assume all vertices of G have degree 3 or 4. If G has 3-vertices only, then mad(G) = 3 and the result follows e.g. from Theorem 4.1. Thus G contains a 4-vertex adjacent to three 3-vertices, a configuration we could deal with the exact same way we dealt with Configuration C5 in the proof of Theorem 4. 1. In what follows, we provide an alternative way to conclude the proof, with different arguments which, we believe, are of independent interest. So G has 4-vertices, minimum degree 3, and the set of the 4-vertices of G must be independent, as otherwise G would have an edge with weight 8. If we denote by H the subgraph of G induced by its 3-vertices, then note that every connected component of H is 2-degenerate. We construct a degenerate 2-labelling ℓ of G by first labelling the edges incident to the 4-vertices, and then labelling the remaining edges of G, those of H.

We start by assigning label 2 to all edges incident to the 4-vertices of G. As a result, we have σ(v) = 8 for every 4-vertex v, while if v is some vertex that is isolated in H, meaning v is a 3-vertex with three 4-neighbours in G, then σ(v) = 6. Particularly, since G does not contain adjacent 4-vertices, at this point we have that if v is a vertex with all its edges being already labelled, then v cannot be contained in some x-cycle.

It remains to label all edges of H. We consider every non-empty connected component H ∈ H in turn, and label its edges as follows. Recall that all vertices of H are 3-vertices of


Emily Tubbs
email: emily.tubbs@cea.fr

Clément Quintard

Amandine Pitaval

Joris Kaal

François Boizot

Yves Fouillet

Fabrice Navarro

Xavier Gidrol

Clément Quintard

Vascularized pancreatic islet-on-chip for type 1 diabetes

teaching and research institutions in France or abroad, or from public or private research centers.

We have previously designed and validated a microfluidic device integrating a network of hyper-elastic valves for automated glucose stimulation and insulin collection from a single pancreatic islet [1]. Here, we used the same serpentine chip design and cultured human beta cells spheroids composed of EndoCBH5 cells (from Human Cell Design©), in a fibrin gel enriched in endothelial cells and fibroblasts. Thus, we tested the effect of flux, and of an enriched vascular microenvironment on the functionality of the human beta cells spheroids. A glucose stimulated insulin secretion assay was performed and we observed an improved functionality of the human beta cells spheroids with both the flux and the enriched microenvironment. Our results confirm that recreating a favorable pancreatic islet niche significantly improves functionality [2].

Our results pave the way to personalized medicine for the study of diabetes. The perspectives offered by this isleton-chip model are considerable and promise to be beneficial to patients.