Julien Bensmail

A notion of vertex equitability for proper labellings

Keywords: irregular labelling, proper labelling, irregularity strength, 1-2-3 Conjecture, equitability

We introduce an equitable version of proper labellings of graphs, where the notion of equitability is with respect to the resulting vertex sums. That is, we are interested in k-labellings where, when computing the sums of labels incident to the vertices, we get a vertex-colouring that is not proper only, but also equitable. For a given graph G, we are interested in the parameter χ Σ (G), which is the smallest k ≥ 1 (if any) such that G admits such k-labellings.

Through examples of particular graph classes, we observe that this new parameter χ Σ behaves sort of similarly to the parameters χ Σ and s, which parameters lie behind the 1-2-3 Conjecture and the irregularity strength of graphs, in a more or less strong way, depending on the graphs considered. We then prove general bounds on χ Σ , showing that, in some contexts (trees and connected graphs with large minimum degree), this parameter is bounded above by roughly 3n 4 for an n-graph. We also prove that determining χ Σ is NP-hard in general, and finish off with directions for further work on the topic.

Introduction

We deal with notions derived from those behind the so-called irregularity strength of graphs and the 1-2-3 Conjecture, which notions relate to distinguishing labellings. For more information on this field, we refer the interested reader to the dynamic survey [START_REF] Gallian | A dynamic survey of graph labeling[END_REF] by Gallian. For the sake of keeping this introduction short, in what follows we only recall the notions and results that are the most important to understand the motivations behind our investigations.

Let G be a graph. A k-labelling ℓ of G is an assignment ℓ ∶ E(G) → {1, . . . , k} of labels (from {1, . . . , k}) to the edges of G. From ℓ, we can compute several metrics of interest for the vertices of G. In this work, we are mostly interested in the sums of labels incident to the vertices. That is, for every vertex v of G, we denote by σ ℓ (v) (or σ(v) for short) the sum of labels assigned to the edges incident to v. Note that this function σ ℓ can be perceived as a vertex-colouring of G. In case all vertices of G have different colours by σ ℓ , or, in other words, all resulting sums are pairwise distinct, we say that ℓ is irregular. Now, in case only all pairs of adjacent vertices of G have different colours by ℓ, or, in other words, if σ ℓ is a proper vertex-colouring of G, then we say that ℓ is proper. The smallest k ≥ 1 (if any) such that G admits irregular k-labellings is denoted by s(G), while the smallest k ≥ 1 (if any) such that G admits proper k-labellings is denoted by χ Σ (G). In the literature, the parameter s(G) is called the irregularity strength of G.

Investigations on irregular and proper labellings were initiated in 1988 by Chartrand et al. in [START_REF] Chartrand | Irregular networks[END_REF], in which the authors deal with a particular practical problem through irregular labellings. Proper labellings were later investigated as a local version of irregular labellings, as Karoński, Łuczak, and Thomason introduced, in [START_REF] Karoński | Edge weights and vertex colours[END_REF], the so-called 1-2-3 Conjecture in 2004. Investigations on both types of objects are still very active nowadays, many questions being still open; notably:

• Generally speaking, the irregularity strength is a parameter that remains very far from being fully understood, even for simple classes of graphs such as trees. Among the most important results on this parameter to date, it was proved by Nierhoff in [START_REF] Nierhoff | A tight bound on the irregularity strength of graphs[END_REF] that s(G) ≤ |V (G)| -1 holds for every nice graph1 G, which is tight in general (consider e.g. any star with at least two leaves). Later on, an important improvement (especially for graphs with large enough minimum degree) over this upper bound was established by Kalkowski, Karoński, and Pfender in [START_REF] Kalkowski | A new upper bound for the irregularity strength of graphs[END_REF], as they proved that s(G) ≤ 6 ⌈ |V (G)| δ(G) ⌉ holds for every nice graph G. We refer the interested reader to [START_REF] Gallian | A dynamic survey of graph labeling[END_REF] for more information on this interesting topic.

• Regarding the parameter χ Σ , the 1-2-3 Conjecture raised in [START_REF] Karoński | Edge weights and vertex colours[END_REF] postulates that we should have χ Σ (G) ≤ 3 for every nice graph G. This is still mostly open to date, as the 1-2-3 Conjecture was mostly proved to hold for 3-colourable graphs [START_REF] Karoński | Edge weights and vertex colours[END_REF]. To date, the most important result towards the conjecture was established by Kalkowski, Karoński, and Pfender in [START_REF] Kalkowski | Vertex-coloring edge-weightings: towards the 1-2-3 Conjecture[END_REF], in which they proved that χ Σ (G) ≤ 5 holds for every nice graph G. Let us mention also that a full proof to the 1-2-3 Conjecture was recently proposed by Keusch in [START_REF] Keusch | A Solution to the 1-2-3 Conjecture[END_REF]. For more details on the 1-2-3 Conjecture, we would advise the reader to refer to [START_REF] Seamone | The 1-2-3 Conjecture and related problems: a survey[END_REF].

Irregular labellings and proper labellings are, by definition, types of objects that are undoubtedly close. This is illustrated, notably, by the facts that these two notions coincide in complete graphs, and that the proofs from [START_REF] Kalkowski | Vertex-coloring edge-weightings: towards the 1-2-3 Conjecture[END_REF] and [START_REF] Kalkowski | A new upper bound for the irregularity strength of graphs[END_REF], in which the best upper bounds on the parameters s and χ Σ to date have been established, exploit similar ideas. They are also rather distant notions, as showcased by the fact that the irregularity strength of disconnected graphs is subject to dedicated studies, while, in the context of the 1-2-3 Conjecture, we can obviously focus on connected graphs.

The general connections between irregular labellings and proper labellings have sometimes been investigated in the literature, through the introduction of intermediate variants. For instance, Przybyło considered in [START_REF] Przybyło | Distant irregularity strength of graphs[END_REF] labellings through which only vertices within a certain fixed distance are required to have distinct sums, and Bensmail, Hocquard, and Marcille considered in [START_REF] Bensmail | Going Wide with the 1-2-3 Conjecture[END_REF] labellings where both the computed sums and the distinction condition are within a certain range. More generally speaking, irregular labellings and proper labellings were derived to a number of variants of varying interest, obtained through playing with the multiple parameters that define them.

In this work, we introduce a new variant of proper labellings, which can be motivated as follows. As mentioned earlier, another way to see proper labellings is to regard them as a way to "encode" proper vertex-colourings. Among other natural questions, one can wonder about similar concerns for other types of vertex-colourings. It is worth mentioning that this thread of research has already been considered in the literature, with variants of proper labellings being considered for e.g. acyclic vertex-colourings [START_REF] Gao | A Relaxed Case on 1-2-3 Conjecture[END_REF], injective vertex-colourings [START_REF] Bensmail | An injective version of the 1-2-3 Conjecture[END_REF], and oriented vertex-colourings [START_REF] Bensmail | Adding Direction Constraints to the 1-2-3 Conjecture[END_REF].

We here initiate the study of a combination of proper labellings and equitable proper vertexcolourings2 , defined formally as follows. Let G be a graph. Given a k-vertex-colouring ϕ ∶ V (G) → {1, . . . , k} of G, for any i ∈ {1, . . . , k} we denote by nb ℓ (i) (or nb(i) for short) the number of vertices v of G verifying ϕ(v) = i. We say that ϕ is equitable if, for any two distinct i, j ∈ {1, . . . , k}, we have |nb(i) -nb(j)| ≤ 1. Now, given a labelling ℓ of G, we derive the notation nb to labellings, as follows: for any i ∈ N + , we denote by nb ℓ (i) (or simply by nb(i)) the number of vertices of G with sum i by ℓ. We now say that ℓ is equiproper if σ ℓ is an equitable proper vertex-colouring of G. In other words, all resulting sums must appear about the same number of times. Finally, we denote by χ Σ (G) the smallest k ≥ 1 such that G admits equiproper k-labellings.

It is worth mentioning that notions of equitability for proper labellings have already been investigated in the literature, namely in [START_REF] Baudon | Equitable neighbour-sum-distinguishing edge and total colourings[END_REF][START_REF] Bensmail | Further Results on an Equitable 1-2-3 Conjecture[END_REF][START_REF] Bensmail | On a combination of the 1-2-3 Conjecture and the Antimagic Labelling Conjecture[END_REF]. However, in those works, the notion of equitablity in question is with respect to how the labels are assigned, and not with respect to the resulting sums. Thus, those works do not relate to the new notions we introduce here.

While, as mentioned above, our original intent for introducing and studying equiproper labellings was to investigate their connections with proper labellings, as will be exposed through our results, it actually turns out that equiproper labellings tend to behave in a way that is more reminiscent of irregular labellings. Thus, equiproper labellings can somewhat be seen as another intermediate notion between irregular labellings and proper labellings. This work is organised as follows. We start in Section 2 by raising first observations and comments on equiproper labellings, which we then investigate in easy classes of graphs, our main goal being to provide a first insight into how these objects behave in general. In Section 3, we then prove that determining χ Σ (G) for a given graph G is NP-complete, a result of a kind that has not been established for the irregularity strength to date, and which we prove through a proof giving yet more hints about the peculiar behaviour of equiproper labellings. In Section 4, we then provide general upper bounds of χ Σ (G) in situations where G has particular properties. Namely, we consider nice trees, and connected graphs with minimum degree at least 4. We conclude in Section 5 with perspectives for further work on the topic.

First look into equiproper labellings, through some classes of graphs

As mentioned earlier, observe that irregular labellings are always equiproper, since, by an irregular labelling ℓ, for every i ∈ N + we have nb(i) ∈ {0, 1}. On the other hand, an equiproper labelling is, by definition, always proper. Thus:

Observation 2.1. If G is a nice graph, then χ Σ (G) ≤ χ Σ (G) ≤ s(G).
This implies that χ Σ (G) is well defined for a graph G if and only if G is nice. From Observation 2.1, we also get that, in order to come up with a graph G for which χ Σ (G) could be "large", maybe a good idea would be to consider a graph with large irregularity strength. As mentioned earlier, we always have s(G) ≤ |V (G)| -1 for a nice graph G (see [START_REF] Nierhoff | A tight bound on the irregularity strength of graphs[END_REF]), and this is known to be tight because of stars. Considering these graphs in our context, we get: Observation 2.2. For a star S n with n ≥ 2 leaves, we have χ Σ (S n ) ≥ ⌈ n 2 ⌉. Proof. Denote by r the n-vertex3 of S n , and by u 1 , . . . , u n its leaves. Note that, by any k-labelling ℓ of S n , we must have σ(r) > σ(u 1 ), . . . , σ(u n ). For this reason, we necessarily have nb(σ(r)) = 1, and, thus, for every i ∈ N + such that nb(i) ≠ 0, we must have nb(i) ∈ {1, 2} for ℓ to be equiproper. Then, by any equiproper k-labelling of S n , any assigned label can be assigned to at most two edges. Thus, we deduce that χ Σ (S n ) ≥ ⌈ n 2 ⌉. Observation 2.2 shows that there is no k ≥ 1 such that χ Σ (G) ≤ k holds for every nice graph G, which might indicate that equiproper labellings are closer to irregular labellings than to proper labellings. In what follows, we investigate equiproper labellings in easy classes of graphs. Our results highlight that, actually, for some graphs the parameter χ Σ can behave very similarly to both s and χ Σ , while, in some contexts, it can be closer to any of the two.

We first observe that, in complete graphs, every proper vertex-colouring must be equitable, as all vertices must get assigned distinct colours. In the context of distinguishing labellings, this implies irregular, proper, and equiproper labellings are equivalent objects in complete graphs.

Observation 2.3. In any complete graph, any irregular labelling is proper and equiproper, and vice versa. Consequently, for every n ≥ 3, we have s(

K n ) = χ Σ (K n ) = χ Σ (K n ),
and thus these three parameters are always equal to 3 (see e.g. [START_REF] Chartrand | Irregular networks[END_REF]).

The example of complete graphs thus shows a peculiar context in which χ Σ , χ Σ , and s behave similarly. The next class we consider, connected graphs with maximum degree 2, or, in other words, paths and cycles, showcases a situation in which χ Σ behaves in a very similar way as χ Σ (with, yet, a slightly different behaviour), and, thus, quite differently from s. Indeed (see e.g. [START_REF] Chang | Vertex-coloring edge-weightings of graphs[END_REF]): Observation 2.4. If P n is any path of order n ≥ 3, then

• χ Σ (P n ) = 1 if n = 3, and • χ Σ (P n ) = 2 otherwise. If C n is any cycle of order n ≥ 3, then • χ Σ (C n ) = 2 if n ≡ 0 mod 4, and • χ Σ (C n ) = 3 otherwise.
In both cases, there is no k ≥ 1 such that s(P n ), s(C n ) ≤ k for every n.

Proof. The last statement follows from the straight observation that, by a k-labelling ℓ of any graph, for a vertex v of degree 2, we have σ(v) ∈ {2, . . . , 2k}. Thus, for ℓ to be irregular in some P n or C n , we need n -2 or n, respectively, to be at most |{2, . . . , 2k}| = 2k -1 so that every 2-vertex can get a distinct sum. Hence, k must be a function of n.

Regarding the value of χ Σ for paths and cycles, recall first that χ Σ (G) = 1 for a graph G if and only if G is locally irregular 4 , and note that P 3 is the only path or cycle with this property. More generally speaking, note also that, by a k-labelling of any graph, a 1-vertex, because we are assigning strictly positive labels only, cannot get the same sum as its unique neighbour. This means that, when designing a proper labelling of a path, we only need to pay attention to the resulting sums for its adjacent 2-vertices.

Note, now, that if u and v are two adjacent 2-vertices, where N (u) = {u ′ , v} and N (v) = {v ′ , u} (where, possibly, u ′ = v ′ ), then, by a labelling ℓ, so that σ(u) ≠ σ(v) we must have ℓ(u ′ u) ≠ ℓ(vv ′ ). Particularly, in a path or a cycle, every two edges at distance 2 apart must receive distinct labels by a proper labelling. From this, we come up with another way to look at proper labellings in paths and cycles. Given a path or a cycle G, let H be the graph obtained by adding a vertex v e for every edge e of G, and adding an edge between any two vertices v e and v f if, in G, edges e and f are at distance exactly 2. By the previous arguments, G admits a proper k-labelling if and only if H admits a proper k-vertex-colouring. The claimed equalities now follow from the fact that, for G being a path or a cycle, H is either an odd-length cycle (when G is a cycle C n with n odd), a disjoint union of two odd-length cycles (when G is a cycle C n with n ≡ 2 mod 4), or a bipartite graph (two disjoint paths when G is a path or a cycle of length 4, or the disjoint union of two even-length cycles when G is a cycle C n with n ≡ 0 mod 4 and n ≥ 8).

For paths and cycles, we start by observing that χ Σ is at least 3 in general. Note that, in the next observation, we do not make explicit the length threshold above which a path or cycle requires the use of labels 1, 2, and 3; while this threshold could probably be retrieved from our arguments, our main intent is actually to establish that labels 1 and 2 do not suffice in general, which is why the upcoming statement is voluntarily vague.

Observation 2.5. If G is a long enough path or cycle, then χ Σ (G) > 2.

Proof. Consider any maximal (non-cycle) path

P = v 1 v 2 . . . v p of G (we have v 1 v p ∈ E(G) if G is a cycle).
For every i ∈ {1, . . . , p -1}, we denote by e i the edge v i v i+1 . Every e i with i odd is said odd, while every e i with i even is said even. Assume now an equiproper 2-labelling ℓ of G exists, and let us focus on the edges of P . For the reasons given in the proof of Observation 2.4, recall that every two "consecutive" even edges e i and e i+2 must be assigned distinct labels by ℓ, and similarly for every two "consecutive" odd edges e i and e i+2 . In some way, this means that ℓ is fully determined by the labels ℓ(e 1 ) and ℓ(e 2 ), and, thus, so are σ(v 2 ), . . . , σ(v p-1 ).

• If ℓ(e 1 ) = ℓ(e 2 ) = 1, then note that (σ(v 2 ), . . . , σ(v p-1 )) = (2, 3, 4, 3, 2, 3, 4, 3, 2, . . . ). That is, we get σ(v i ) = 3 for every odd i ∈ {3, . . . , p -1}, while we get σ(v i ) = 2 for every even i ∈ {2, . . . , p-1} with i ≡ 2 mod 4 and σ(v i ) = 4 for every even i ∈ {4, . . . , p-1} with i ≡ 0 mod 4.

• If ℓ(e 1 ) = ℓ(e 2 ) = 2, then (σ(v 2 ), . . . , σ(v p-1 )) = (4, 3, 2, 3, 4, 3, 2, 3, 4, . . . ). That is, we get σ(v i ) = 3 for every odd i ∈ {3, . . . , p -1}, while we get σ(v i ) = 4 for every even i ∈ {2, . . . , p -1} with i ≡ 2 mod 4 and σ(v i ) = 2 for every even i ∈ {4, . . . , p -1} with i ≡ 0 mod 4.

• If (ℓ(e 1 ), ℓ(e 2 )) = (1, 2), then (σ(v 2 ), . . . , σ(v p-1 )) = (3, 4, 3, 2, 3, 4, 3, 2, 3, . . . ). That is, we get σ(v i ) = 3 for every even i ∈ {2, . . . , p -1}, while we get σ(v i ) = 4 for every odd i ∈ {3, . . . , p -1} with i ≡ 3 mod 4 and σ(v i ) = 2 for every odd i ∈ {5, . . . , p -1} with i ≡ 1 mod 4.

• If (ℓ(e 1 ), ℓ(e 2 )) = (2, 1), then (σ(v 2 ), . . . , σ(v p-1 )) = (3, 2, 3, 4, 3, 2, 3, 4, 3, . . . ). That is, we get σ(v i ) = 3 for every even i ∈ {2, . . . , p -1}, while we get σ(v i ) = 2 for every odd i ∈ {3, . . . , p -1} with i ≡ 3 mod 4 and σ(v i ) = 4 for every odd i ∈ {5, . . . , p -1} with i ≡ 1 mod 4.

In all cases, it can thus be noted that nb(3) is about twice nb(2) and nb(4). Thus, assuming G is long enough, and because P is a longest path of G, we deduce that ℓ cannot be equiproper.

Due to Observation 2.5 one could wonder whether χ Σ can be arbitrarily large for a given path or cycle, especially when taking into account that such large graphs have a lot of vertices with the same degree, 2, meaning that, by a k-labelling with k relatively small, the range of possibly sums for the vertices is small too. It turns out that χ Σ is always at most 3 for any nice path or cycle. So, while χ Σ and χ Σ are not always equal for such graphs, χ Σ is yet much closer to χ Σ than to s.

Theorem 2.6. If G is a nice path or cycle, then χ Σ (G) ≤ 3.
Proof. Note that given a proper vertex-colouring of H, the graph obtained from G as described in the proof of Observation 2.4, it is far from obvious what sums will be obtained for the vertices of G, by the corresponding labelling. For these reasons, we instead describe how to construct an equiproper 3-labelling of G right away from scratch, depending on what the length of G is. Also, to avoid dealing with pathological cases, in what follows we assume that G is long enough (thereby getting that Observation 2.5 cannot be made worse); by that, we mean of length at least 12. It is not too complicated to check by hand that the claim also holds for smaller length values.

Assume first that G is a path (v 1 , . . . , v n ). For every i ∈ {1, . . . , n -1}, we denote by e i the edge v i v i+1 . We consider three cases.

• |E(G)| ≡ 2 mod 3 (with |E(G)| ≥ 8).
In this case, assign labels 3, 2, and 2 to e 1 , e 2 , and e 3 , respectively, and, from here on, while possible, repeatedly pick the next three unlabelled edges e i , e i+1 , and e i+2 , and assign labels 1, 3, and 2, respectively, to them, until e n-3 gets labelled (thus with label 2). Finally, assign labels 2 and 3 to e n-2 and e n-1 , respectively. By the resulting 3-labelling of G, note that σ(v 1 ) = 3, σ(v 2 ) = 5, and σ(v 3 ) = 4. Meanwhile, we get σ(v n-2 ) = 4, σ(v n-1 ) = 5, and σ(v n ) = 3. Also, for every i ∈ {4, . . . , n -3}, we have σ

(v i ) = 3 if i ≡ 1 mod 3, σ(v i ) = 4 if i ≡ 2 mod 3, and σ(v i ) = 5 if i ≡ 0 mod 3. Since |E(G)| ≡ 2 mod 3, note that n ≡ 0 mod 3.
From these arguments, we thus deduce that nb(3) = nb(4) = nb(5) while all vertices have sum in {3, 4, 5}, and the resulting 3-labelling is thus equiproper. In particular, its properness follows from the fact that no two edges at distance 2 of G are assigned the same label.

• |E(G)| ≡ 0 mod 3 (with |E(G)| ≥ 12).
Apply the same 3-labelling process as in the previous step (that is, assign labels 3, 2, and 2 to e 1 , e 2 , and e 3 , before repeatedly assigning labels 1, 3, and 2 to consecutive triples of unlabelled edges e i , e i+1 , and e i+2 ), but stop when e n-7 is labelled. Now, assign labels 2, 1, 3, 2, 2, and 3 to e n-6 , . . . e n-1 , respectively. As in the previous case, we get σ(v 1 ) = 3, σ(v 2 ) = 5, and σ(v 3 ) = 4, and for every i ∈ {4, . . . , n -7}, we have σ

(v i ) = 3 if i ≡ 1 mod 3, σ(v i ) = 4 if i ≡ 2 mod 3, and σ(v i ) = 5 if i ≡ 0 mod 3. Particularly, because |E(G)| ≡ 0 mod 3, note that e n-7
was assigned label 2. Also, σ(v n-7 ) = 5. Note now that, due to how we finished the labelling, we have σ [START_REF] Bensmail | Going Wide with the 1-2-3 Conjecture[END_REF], while all vertices have sum in {3, 4, 5}. Also, no two edges of G at distance 2 are assigned the same label. The resulting 3-labelling of G is thus equiproper.

(v n-6 ) = 4, σ(v n-5 ) = 3, σ(v n-4 ) = 4, σ(v n-3 ) = 5, σ(v n-2 ) = 4, σ(v n-1 ) = 5, and σ(v n ) = 3. So, we have nb(4) -1 = nb(3) = nb
• |E(G)| ≡ 1 mod 3 (with |E(G)| ≥ 7).
In this case, for every i ∈ {1, . . . , n -5}, assign label 3 to e i if i ≡ 1 mod 3, label 2 to e i if i ≡ 2 mod 3, and label 1 to e i if i ≡ 0 mod 3. Lastly, assign label 3, 2, 2, and 3 to e n-4 , e n-3 , e n-2 , and e n-1 , respectively. As a result, σ(v 1 ) = 3, while, for every i ∈ {2, . . . , n -5}, we have σ

(v i ) = 5 if i ≡ 2 mod 3, σ(v i ) = 3 if i ≡ 0 mod 3, and σ(v i ) = 4 if i ≡ 1 mod 3. Also, σ(v n-5 ) = 3.
Due to how we labelled the last edges, note that we also have σ

(v n-4 ) = 4, σ(v n-3 ) = 5, σ(v n-2 ) = 4, σ(v n-1 ) = 5, and σ(v n ) = 3.
From these arguments, we deduce that Now consider the case where G is a cycle (v 0 , . . . , v n-1 , v 0 ). For every i ∈ {0, . . . , n-1}, we denote by e i the edge v i v i+1 (where operations over the subscripts, here and further, are modulo n). Once again, we consider a few cases (see Figure 1 for an illustration).

• If |E(G)| ≡ 0 mod 5 (with |E(G)| ≥ 5), then we consider every i ∈ {0, . . . , n -1}, and assign label 1 to e i if i ≡ 0, 1 mod 5, label 2 to e i if i ≡ 2 mod 5, and label 3 to e i otherwise, if i ≡ 3, 4 mod 5. As a result, for every i ∈ {0, . . . , n -1}, we get σ [START_REF] Bensmail | Adding Direction Constraints to the 1-2-3 Conjecture[END_REF], and all sums are in {2, 3, 4, 5, 6}. Also, no edges at distance 2 are assigned the same label. Then, the 3-labelling is equiproper.

(v i ) = 2 if i ≡ 1 mod 5, σ(v i ) = 3 if i ≡ 2 mod 5, σ(v i ) = 5 if i ≡ 3 mod 5, σ(v i ) = 6 if i ≡ 4 mod 5, and σ(v i ) = 4 if i ≡ 0 mod 5. Then, nb(2) = nb(3) = nb(4) = nb(5) = nb
• If |E(G)| ≡ 1 mod 5 (with |E(G)| ≥ 11
), then we consider every i ∈ {0, . . . , n -7}, and as in the previous case assign label 1 to e i if i ≡ 0, 1 mod 5, label 2 to e i if i ≡ 2 mod 5, and label 3 to e i otherwise, if i ≡ 3, 4 mod 5. Finally, we assign labels 1, 1, 2, 2, 3, and 3 to e n-6 , e n-5 , e n-4 , e n-3 , e n-2 , and e n-1 , respectively. Then, for every i ∈ {1, . . . , n -7}, we get σ

(v i ) = 2 if i ≡ 1 mod 5, σ(v i ) = 3 if i ≡ 2 mod 5, σ(v i ) = 5 if i ≡ 3 mod 5, σ(v i ) = 6 if i ≡ 4 mod 5, and σ(v i ) = 4 if i ≡ 0 mod 5. Also, σ(v 0 ) = 4, σ(v n-1 ) = 6, σ(v n-2 ) = 5, σ(v n-3 ) = 4, σ(v n-4 ) = 3, σ(v n-5 ) = 2, and σ(v n-6 ) = 4. Then, nb(2) = nb(3) = nb(5) = nb(6), while nb(2) = nb(4) -1.
Also all vertices of G have sum in {2, 3, 4, 5, 6} and no two edges at distance 2 are assigned the same label. Then, the resulting 3-labelling of G is equiproper.

• If |E(G)| ≡ 2 mod 5 (with |E(G)| ≥ 7
), then we consider every i ∈ {0, . . . , n -3}, and as in the previous cases assign label 1 to e i if i ≡ 0, 1 mod 5, label 2 to e i if i ≡ 2 mod 5, and label 3 to e i otherwise, if i ≡ 3, 4 mod 5. Finally, we assign label 2 to e n-2 and e n-1 . Then, for every i ∈ {1, . . . , n -3}, we get σ Also all vertices of G have sum in {2, 3, 4, 5, 6} and no two edges at distance 2 are assigned the same label. Then, the resulting 3-labelling of G is equiproper.

(v i ) = 2 if i ≡ 1 mod 5, σ(v i ) = 3 if i ≡ 2 mod 5, σ(v i ) = 5 if i ≡ 3 mod 5, σ(v i ) = 6 if i ≡ 4 mod 5, and σ(v i ) = 4 if i ≡ 0 mod 5. Also, σ(v 0 ) = 3, σ(v n-1 ) = 4,
• If |E(G)| ≡ 3 mod 5 (with |E(G)| ≥ 8
), then we consider every i ∈ {0, . . . , n -4}, and as previously assign label 1 to e i if i ≡ 0, 1 mod 5, label 2 to e i if i ≡ 2 mod 5, and label 3 to e i otherwise, if i ≡ 3, 4 mod 5. Finally, we assign label 1 to e n-3 , label 2 to e n-2 , and label 3 to e n-1 . Then, for every i ∈ {1, . . . , n-4}, we get σ 5), and nb(2) = nb(6) + 1. Also all vertices of G have sum in {2, 3, 4, 5, 6} and no two edges at distance 2 are assigned the same label. Then, the resulting 3-labelling of G is equiproper.

(v i ) = 2 if i ≡ 1 mod 5, σ(v i ) = 3 if i ≡ 2 mod 5, σ(v i ) = 5 if i ≡ 3 mod 5, σ(v i ) = 6 if i ≡ 4 mod 5, and σ(v i ) = 4 if i ≡ 0 mod 5. Also, σ(v 0 ) = 4, σ(v n-1 ) = 5, σ(v n-2 ) = 3,
v i ) = 2 if i ≡ 1 mod 5, σ(v i ) = 3 if i ≡ 2 mod 5, σ(v i ) = 5 if i ≡ 3 mod 5, σ(v i ) = 6 if i ≡ 4 mod 5, and σ(v i ) = 4 if i ≡ 0 mod 5. Also, σ(v 0 ) = 4, σ(v n-1 ) = 5, σ(v n-2 ) = 3, σ(v n-3 ) = 2, and σ(v n-4 ) = 4. Then, nb(2) = nb(3) = nb(4) = nb(
Turning to complete bipartite graphs now, we recall the following (see e.g. [START_REF] Chang | Vertex-coloring edge-weightings of graphs[END_REF]):

Observation 2.7. If K s,t is a complete bipartite graph with parts of cardinality s and t (with

s + t ≥ 3), then • χ Σ (K s,t ) = 1 if s ≠ t, and
• χ Σ (K s,t ) = 2 otherwise.
Furthermore, there is no k ≥ 1 such that s(K s,t ) ≤ k for every s, t.

Proof. The first item is because K s,t is locally irregular when s ≠ t. When s = t, a proper 2-labelling can be obtained by choosing any vertex v of K s,t , assigning label 2 to all edges incident to v, and assigning label 1 to all other edges. The last claim follows from the same reason as in the proof of Observation 2.4. Particularly, if s = 2, then, so that the t vertices with degree 2 can have pairwise distinct sums by any irregular k-labelling of K s,t , we must have |{2, . . . , 2k}| = 2k -1 ≥ t. Thus, k must be a function of s and t.

Contrarily to the case of paths and cycles (recall Theorem 2.6), it turns out that χ Σ , in the context of complete bipartite graphs, has a behaviour that is more reminiscent of that of the irregularity strength, in the following sense: Observation 2.8. There is no k ≥ 1 such that χ Σ (K s,t ) ≤ k for every s, t (with s + t ≥ 3).

Proof. For some s and t, let (U, V ) denote the bipartition of K s,t where |U | = s and |V | = t, and s ≤ t. Then, d(u) = t for every u ∈ U , and d(v) = s for every v ∈ V .

Fix now any k ≥ 1, and assume e.g. that t > (s + 1)ks. Note that, by any k-labelling ℓ of K s,t , we have σ(u) ≥ d(u) = t for every u ∈ U , and σ(v) ≤ kd(v) = ks for every v ∈ V . Particularly, since t > (s + 1)ks, we have t > ks, and thus a vertex of U cannot have the same sum as a vertex of V . For this reason, if ℓ is equiproper, then, for every u ∈ U , we must have nb(σ(u)) ≤ |U | = s. This means that, for any i ∈ N + such that nb(i) > 0, we have nb(i) ≤ s + 1. Now, the vertices v ∈ V have sum in {s, . . . , ks}, which is a set of cardinality (k -1)s + 1. Particularly, since t > (s + 1)ks, we have t > (s + 1)((k -1)s + 1), and thus for some vertex v in V we must have nb(σ(v)) > s + 1, which contradicts that ℓ is equiproper. Since this holds for every k ≥ 1, the claim follows.

Complexity aspects

We now consider the complexity of the problem of determining χ Σ (G) for a given graph G. Unsurprisingly (see below), we prove this problem to be NP-complete. One of the main points of interest behind our result actually lies in the forcing mechanisms we develop to establish it, which allows to get further understanding over equiproper labellings.

For record, recall that deciding whether χ Σ (G) ≤ 2 holds for a given graph G was proved to be NP-complete [START_REF] Dudek | On the complexity of vertex-coloring edge-weightings[END_REF]. On the other hand, we still do not know whether the similar result holds for the irregularity strength, as exposed in [START_REF] Bensmail | On the hardness of determining the irregularity strength of graphs[END_REF], in which hints on this question are provided. For other variants lying in between irregular labellings and proper labellings, such NP-completeness results were also established (see e.g. [START_REF] Bensmail | Going Wide with the 1-2-3 Conjecture[END_REF]). This is also the case for other variants dealing with equitability, but with respect to the assigned labels, see [START_REF] Bensmail | Further Results on an Equitable 1-2-3 Conjecture[END_REF].

Our result, now, reads as follows:

Theorem 3.1. Deciding whether χ Σ (G) ≤ 2 holds for a given graph G is NP-complete.

Proof. Since the problem is clearly in NP, we focus on proving its NP-hardness. This is done by reduction from the Cubic Monotone 1-in-3 SAT problem, which was proved to be NP-hard in [START_REF] Moore | Hard Tiling Problems with Simple Tiles[END_REF]. Recall that an instance of Cubic Monotone 1-in-3 SAT is a 3CNF formula F over clauses C 1 , . . . , C m and variables x 1 , . . . , x n , where all clauses of F contain exactly three distinct (positive) variables, and all variables appear (in positive form) in exactly three distinct clauses each. The question is whether F can be 1-in-3 satisfied, i.e., whether there is a truth assignment to the variables such that every clause contains exactly one true variable (thus together with two false ones). Given such an F , we construct, in polynomial time, a graph G such that F is 1-in-3 satisfiable if and only if G admits equiproper 2-labellings. By definition of Cubic Monotone 1-in-3 SAT, note that the graph G F modelling the structure of F (in which there is a clause vertex v C associated to every clause C, a variable vertex v x associated to every variable x, and a formula edge v C v x whenever variable x belongs to clause C) is cubic, and thus we must have n = m, i.e., the number of variables equals the number of clauses. We can also assume n is even, as, clearly, F is 1-in-3 satisfiable if and only if F ∧ (x ∨ x ′ ∨ x ′′ ) ∧ (x ∨ x ′ ∨ x ′′ ) ∧ (x ∨ x ′ ∨ x ′′ ) (where x, x ′ , and x ′′ are new variables) is 1-in-3 satisfiable, and the latter formula has three more clauses each containing three distinct (positive) variables, and three more variables each appearing (in positive form) in three distinct clauses.

We define F as the formula being the negation of F , having a clause C i = (x i1 ∧ x i2 ∧ x i3 ) for every clause C i = (x i1 ∧ x i2 ∧ x i3 ) of F , being defined over the n negated variables x 1 , . . . , x n . Note that F also has n clauses and n (negated) variables, and F is 1-in-3 satisfiable if and only if F is. Now set Φ = F ∧ F . Thus, Φ is a 3CNF cubic formula with 2n clauses C 1 , . . . , C n , C 1 , . . . , C n defined over 2n literals x 1 , . . . , x n and x 1 , . . . , x n . We actually construct a graph G from Φ, such that Φ is 1-in-3 satisfiable if and only if G admits equiproper 2-labellings. Note that this yields the desired equivalence between F and G.

The construction of G goes as follows (see Figure 2). • We now add edges incident to the d i 's and e i 's, going to the a i 's, b i 's, c i 's, and vertices of G Φ . We call 1-edges the edges incident to the d i 's we will add, and 2-edges those incident to the e i 's. Essentially, the point is that, due to the eventual structure of G, in any equiproper 2-labelling, the 1-edges will necessarily be assigned label 1, while the 2-edges will necessarily be assigned label 2. We add these edges so that 1) the degrees of the d i 's grow equally, 2) the degrees of the e i 's grow equally, and 3) the degrees of the d i 's are about twice those of Numbers near 1-edges and 2-edges incident to some vertex indicate how many 1-edges and 2-edges are incident to that vertex. For legibility reason, note that not all edges are drawn. Particularly, in this illustration, the 1-edges and 2-edges incident to p 1 , q 1 , and r 1 depict the case where we must add at least two 1-edges and at least two 2-edges incident to the d i 's and e i 's. On the other hand, there are no 1-edges and 2-edges incident to p 21n+1 , q 21n+1 , and r 21n+1 , which corresponds to the case where no 1-edges and 2-edges miss.

G Φ vC 1 vC 2 vC n vx 1 vx 2 vx n v C ′ 1 v C ′
the e i 's. To guarantee most of these conditions, we proceed in the following way. In what follows, when needing to attach a 1-edge at some vertex u (being neither a d i nor an e i ) for the first time, we add d 1 u. Later on, assuming we need to attach another 1-edge at some u, then, assuming the last added 1-edge is incident to d i , we add d i+1 u, where d 1 is regarded as d 21n 2 +1 . In some sense, we add edges incident to the d i 's in a balanced way, cycling through the ordering d 1 , . . . , d 21n 2 . We add 2-edges the same way, except they are incident to the e i 's. Now, the 1-edges and 2-edges we add are the following:

-To every clause vertex, we attach eight 1-edges and four 2-edges.

-To every literal vertex, we attach two 1-edges and one 2-edge.

-To every a i , we attach ten 1-edges and five 2-edges.

-To every b i , we attach four 1-edges and two 2-edges.

-To every c i , we attach five 1-edges and three 2-edges.

• Note that the number of 1-edges we attached is 16n (clause vertices) + 4n (literal vertices) + 180n (a i 's) + 80n (b i 's) + 100n (c i 's), that is, 380n. Meanwhile, the number of 2-edges we attached is 8n (clause vertices) + 2n (literal vertices) + 90n (a i 's) + 40n (b i 's) + 60n (c i 's), that is, 200n. Then, (2 × 200n) -380n = 20n, which means that if we wanted the number of 1-edges (and thus the sum of the degrees of the d i 's) to be twice the number of 2-edges (and thus the sum of the degrees of the e i 's), then 20n more 1-edges would need to be added.

We add n more a i 's, denoted by a 18n+1 , . . . , a 19n , to each of which we attach 20 1-edges. As a result, the number of attached 1-edges is now 400n, twice that of attached 2-edges, 200n.

In terms of degrees, note that the clause vertices have degree 15 (recall the formula edges), the literal vertices have degree 6, the a i 's have degree 15 (a 1 , . . . , a 18n ) or 20 (a 18n+1 , . . . , a 19n ), the b i 's have degree 6, and the c i 's have degree 8. Also, besides the d i 's and the e i 's, vertices are incident to at most 20 1-edges or 2-edges of the same type, meaning that the process above keeps the graph simple, assuming 21n 2 > 20 (which we can assume, as otherwise F would be of constant size, and its 1-in-3 satisfiability could be determined in constant time).

On the other hand, note that 38 < 400n < 20. Due to how we have added 1-edges and 2-edges (in a balanced and equitable way), this implies the d i 's have degree in {38, 39}, while the e i 's have degree in {19, 20}. So, for now, the d i 's are the vertices of G with the largest degrees; a problem, however, is that their degrees are not large enough, in the sense that, besides the e i 's, some other vertices could reach the same sums by a 2-labelling. In particular, note that some of the a i 's have degree 20. In what follows, we add more structure to the graph to make the degrees of the d i 's and e i 's a bit larger. What we desire, is that, by a 2-labelling of G, only the e i 's can have the same sums as the d i 's.

• We now add 21n new vertices f 1 , . . . , f 21n to the graph, joined to the d i 's and e i 's as follows.

We arrange the f i 's into the 21n 2 pairs P 1 = {f 1 , f 2 }, P 2 = {f 3 , f 4 }, P 3 = {f 5 , f 6 }, and so on. Now, for every i ∈ {1, . . . , 21n 2 }, we add four 1-edges incident to d i , going to the four vertices in the pairs P i and P i+1 (where, naturally, P 21n 2 +1 = P 1 ). As a result, the d i 's are each joined to four f i 's, while the f i 's are each incident to two 1-edges. Thus, the d i 's now have degree in {42, 43}. Similarly, for every i ∈ {1, . . . , 21n 2 }, we add two 2-edges incident to e i , going to the two vertices in P i . The e i 's are thus each joined to two f i 's, and each f i is incident to exactly one 2-edge; thus, the e i 's now have degree in {21, 22}, while the f i 's are now incident to both two 1-edges and one 2-edge.

• Our goal, now, is to add a few edges incident to the d i 's and to the e i 's so that all d i 's have degree 44, while all e i 's have degree 22. We do so while adding some more structure to the graph to ensure some forcing mechanisms. More precisely, we add edges incident to the d i 's and e i 's going to new vertices (p i 's, q i 's, and r i 's below), in such a way the resulting degrees for these new vertices remain small.

Formally, for every i ∈ {1, . . . , 21n + 1}, we start by adding three new vertices p i , q i , and r i to the graph, isolated for now. We then add some more 1-edges and 2-edges, in the manner described below to reach the desired properties.

Note that to reach the desired degrees, some of the d i 's miss two incident edges, while all of the others miss only one incident edge. Regarding the e i 's, some of them miss exactly one incident edge, while the others miss none. Particularly, the total number of missing 1-edges is thus larger than the total number of missing 2-edges. Also, since there are 21n 2 d i 's and 21n 2 e i 's, the number of missed edges is at most 3 × 21n 2 . Free to rename the d i 's and e i 's, we may assume that there are α, β ∈ {0, . . . , 21n 2 } such that the first α d i 's miss two incident edges while the others miss only one, and that the first β e i 's miss one incident edge while the others do not. In what follows, when adding missing 1-edges and 2-edges (going to the p i 's, q i 's, and r i 's), we do so following this ordering over the d i 's and e i 's; that is, the first α 1-edges we add are incident to d 1 , . . . , d α , while the first β 2-edges we add are incident to e 1 , . . . , e β (where, again, after considering d 21n 2 and e 21n 2 , the next vertices to be considered are d 1 and e 1 , respectively). This guarantees we first deal with the d i 's and e i 's that miss the most edges. Also, this guarantees, whenever attaching two 1-edges at some vertex, that they do not originate from the same d i (so that the graph remains simple).

The process now goes as follows. As long as there remain 1-edges and 2-edges (incident to the d i 's and e i 's) to be added, we consider a new value of i ∈ {1, . . . , 21n + 1}, and add new 1-edges and 2-edges going from the next (following the ordering above) faulty d i 's and e i 's and going to vertices in {p i , q i , r i }. Since we want to keep control over the degrees of p i , q i , and r i , this is done in multiple possible ways, depending on the number of 1-edges and 2-edges that remain to be added. Now, consider every i ∈ {1, . . . , 21n + 1} in turn; then:

1. If, in total, at least two 2-edges miss, then there also miss at least two 1-edges. Then, we add a 1-edge incident to p i , a 2-edge incident to q i , and both a 1-edge and a 2-edge incident to r i (see Figure 2). Note that p i and q i get degree 1, while r i gets degree 2.

If exactly one 2-edge misses:

-If exactly one 1-edge misses, then we add a 1-edge incident to p i and a 2-edge incident to q i . Note that p i and q i get degree 1, while r i remains of degree 0. -If exactly two 1-edges miss, then we add a 1-edge incident to p i , and both a 1-edge and a 2-edge incident to r i . Note that p i gets degree 1, q i remains of degree 0, while r i gets degree 2.

-If exactly three 1-edges miss, then we add three 1-edges incident to r i , and a 2-edge incident to q i . Note that p i remains of degree 0, q i gets degree 1, while r i gets degree 3. -If at least four 1-edges miss, then we add a 1-edge incident to p i , a 2-edge incident to q i , and three 1-edges incident to r i . Note that p i and q i get degree 1, while r i gets degree 3.

3. If no 2-edges miss but some 1-edges miss:

-If exactly one 1-edge misses, then we add a 1-edge incident to p i . Note that p i gets degree 1, while q i and r i remain of degree 0. -If at least two 1-edges miss, then we add one 1-edge incident to p i , one 1-edge incident to r i , and we add the edge q i r i . Note that p i and q i get degree 1, while r i gets degree 2 (★).

4. If no 2-edges and no 1-edges miss, then we add the edges p i r i and q i r i (see Figure 2). Note that p i and q i get degree 1, while r i gets degree 2. In that case, note that {p i , q i , r i } induces a path of length 2 which is isolated from the rest of the graph; we say this set {p i , q i , r i } is isolated.

Once this process achieves, note that all p i 's and q i 's have degree 1, except maybe for one (isolated) of them. Meanwhile, all d i 's have degree 44, and all e i 's have degree 22, as intended. Above, we have also marked (with ★) one particular case (which might occur several times) in which the treatment is a bit peculiar, as, besides 1-edges and 2-edges, for some i we also had to add one edge joining some vertices in {p i , q i , r i } (while {p i , q i , r i } is not isolated). This case being handled differently from the others, it will be commented upon in the upcoming analysis. Note also that, since n can be assumed to be large enough, the first case above must have occurred at least once; particularly, we might assume r 1 is incident to exactly one 1-edge and exactly one 2-edge. Also, it can be checked that at most one of the r i 's is isolated.

• Last, to achieve the construction of G, for every i ∈ {1, . . . , n}, we add the edge v xi v xi .

The graph we have obtained at this point is our G. Clearly, the whole construction is achieved in polynomial time. We now prove a few claims. Claim 3.2. If ℓ is any equiproper 2-labelling of G, then, for every i ∈ N + such that nb(i) ≠ 0, we have nb(i) ∈ {21n, 21n + 1}.

Proof of the claim. Recall that at most one of the p i 's and q i 's is not of degree 1, and that these vertices are the only 1-vertices of G. Since there are 21n + 1 p i 's and 21n + 1 q i 's, this means the number of 1-vertices of G lies in {42n+1, 42n+2}. Also, by any 2-labelling, recall that any 1-vertex has sum in {1, 2}. For these reasons, by any equiproper 2-labelling ℓ of G, at least one of nb(1) and nb(2) must be at least 21n + 1.

Note also that the maximum degree of a vertex in G is 44, which is achieved by the d i 's. Furthermore, besides the d i 's, the vertices that have the largest degree are the e i 's, which have degree 22. Recall that there are 21n 2 d i 's, and 21n 2 e i 's, thus 21n d i 's and e i 's in total. Also, by any 2-labelling, the d i 's have sum in {44, . . . , 88}, while the e i 's have sum in {22, . . . , 44}, and all other vertices have sum strictly less than 44. Thus, for every i ∈ {45, . . . , 88}, we necessarily have nb(i) ≤ 21n 2 , while nb(44) can be as large as 21n (which occurs when all d i 's and e i 's have sum 44). From these arguments, we deduce that, by any equiproper 2-labelling of G, we must have nb(i) = 0 for every i ∈ {45, . . . , 88} and nb(44) > 0. Furthermore, so that nb(44) and either nb(1) or nb(2) are not too distant (i.e., their difference is at most 1), we must have nb(44) = 21n, while the largest of nb(1) and nb(2) must be 21n + 1. This implies that, for every i ∈ N + such that nb(i) ≠ 0, we must have nb(i) ∈ {21n, 21n + 1}. ◇ Claim 3.3. In every equiproper 2-labelling ℓ of G, all 1-edges must be assigned label 1, and all 2-edges must be assigned label 2.

Proof of the claim. As mentioned in the proof of Claim 3.2, we must have nb(44) = 21n, and this requires all d i 's and all e i 's to have sum 44 by ℓ. Since all d i 's have degree 44 and all e i 's have degree 22, we deduce that all edges incident to the d i 's must be assigned label 1, while all edges incident to the e i 's must be assigned label 2. ◇ Claim 3.4. In every equiproper 2-labelling ℓ of G:

• all a i 's have sum 20;

• all b i 's have sum 8;

• all c i 's have sum 11;

• all d i 's and e i 's have sum 44;

• all f i 's have sum 4;

• for every set {p i , q i , r i }:

if {p i , q i , r i } is not isolated, then σ(p i ) = 1, σ(q i ) = 2, and σ(r i ) = 3;

if {p i , q i , r i } is isolated, then either {σ(p i ), σ(q i )} = {1, 2} and σ(r i ) = 3, or σ(p i ) = σ(q i ) ∈ {1, 2} and σ(r i ) ∈ {2, 4}; furthermore, in the latter situation, {p i , q i , r i } is the only isolated set with these properties.

Particularly, nb( 20 Proof of the claim. The first part follows mainly from Claim 3.3, since most of the edges incident to these vertices are 1-edges and 2-edges. Actually, besides isolated sets {p i , q i , r i }, the only case in which these vertices are not incident to 1-edges and 2-edges only, is that of two vertices q i and r i joined by an edge, which occurred when we dealt with the case marked with ★ above. Note that case ★ might have occurred several times. We claim, however, that for any i such that case ★ applied, we must have ℓ(q i r i ) = 2. Assume indeed that we have ℓ(q i r i ) = 1 for some such i. Then σ(r i ) = 2 due to a 1-edge incident to r i . If the number of 1-vertices of G was 42n + 2, then we would deduce that there are at least 42n + 3 vertices with sum in {1, 2}, and thus that either nb(1) or nb(2) must be at least 21n + 2, a contradiction to Claim 3.2. So, the number of 1-vertices of G must be 42n+1, and we must have nb(1) = nb(2) = 21n+1. For this to happen, note that must have ended up adding 1-edges and 2-edges with the case right before that marked with ★. The application of this case implies there is some j > i such that both q j and r j are isolated. Thus, the number of non-isolated r i 's is exactly 21n. Meanwhile, note that, due to the 1-edges and 2-edges we have added, only the r i 's can have sum 3, and we know for sure that σ(r 1 ) = 3, i.e., there are vertices with sum 3. Since σ(r i ) = 2, we thus deduce that nb(3) < 21n, a contradiction to Claim 3.2. Thus, we have ℓ(q i r i ) = 2 as claimed, and, for all i such that {p i , q i , r i } is not isolated, we have σ(p i ) = 1, σ(q i ) = 2, and σ(r i ) = 3, due to the 1-edges and 2-edges.

In the case of an isolated set {p i , q i , r i }, note that there are, essentially, two main ways to 2-label it: either ℓ(p i r i ) = ℓ(q i r i ), or ℓ(p i r i ) ≠ ℓ(q i r i ). In the former case, note that this yields σ(r i ) ∈ {2, 4}, while, in the latter case, this yields σ(r i ) = 3. As mentioned earlier, the number of non-isolated r i 's is 21n or 21n + 1, for every j such that {p j , q j , r j } and r j are not isolated we have σ(r j ) = 3, and the only vertices of G which can have sum 3 are the non-isolated r i 's. If the number of non-isolated r i 's is 21n, then, so that nb(3) does not contradict Claim 3.2, we deduce that, for every isolated {p i , q i , r i }, we must have ℓ(p i r i ) ≠ ℓ(q i r i ), which yields {σ(p i ), σ(q i )} = {1, 2} and σ(r i ) = 3. Now, if the number of non-isolated r i 's is 21n + 1, then either ℓ(p i r i ) ≠ ℓ(q i r i ) for every isolated {p i , q i , r i } and we reach the same conclusion, or there exists exactly one i (as otherwise we would have nb(3) < 21n) such that {p i , q i , r i } is isolated and ℓ(p i r i ) = ℓ(q i r i ). In that precise last case, we have the conclusions described in the statement. Particularly, note that if σ(r i ) = 4, then nb(4) = 21n + 1 (as, besides r i , only the f i 's can have sum 4).

Regarding the very last part of the statement, it follows from the number of a i 's, b i 's, c i 's, d i 's, e i 's, f i 's, p i 's, q i 's, and r i 's in G, and from arguments given in the proof of Claim 3.3. ◇ Claim 3.5. In every equiproper 2-labelling ℓ of G:

• for every clause vertex v C , we have σ(v C ) = 20;

• for every two opposite literal vertices v x and v x , we have {σ(v x ), σ(v x )} = {8, 11}.

Particularly, every clause vertex must be incident to two formula edges assigned label 1 and one formula edge assigned label 2, while every literal vertex must have its three incident formula edges assigned the same label. Also, any two opposite literal vertices v x and v x must assign distinct labels to their respective incident formula edges.

Proof of the claim. Recall that, by construction, v C is incident to eight 1-edges and four 2-edges, while v x and v x are adjacent and each incident to two 1-edges and one 2-edge. By Claim 3.3, recall that all 1-edges must be assigned label 1 by ℓ, while all 2-edges must be assigned label 2. Since all clause vertices and literal vertices are also each incident to three formula edges (which can each be assigned label 1 or 2), we must have σ(v C ) ∈ {19, 20, 21, 22} and σ(v x ), σ(v x ) ∈ {8, 9, 10, 11, 12}.

Particularly, note that a clause vertex and a literal vertex cannot have the same sum. Now, recall that, by Claim 3.4, all 19n a i 's must have sum 20 by ℓ, all 20n b i 's must have sum 8, and all 20n c i 's must have sum 11. Meanwhile, recall that, by Claim 3.2, for every i ∈ N + such that nb(i) ≠ 0, we have nb(i) ∈ {21n, 21n + 1}. Then, so that, nb(20) ∈ {21n, 21n + 1}, it must be that the 2n clause vertices have sum 20, to get 21n vertices with sum 20 in total. This requires every clause vertex to be incident to exactly one formula edge assigned label 2, while the other two must be assigned label 1. Likewise, so that nb(8), nb(11) ∈ {21n, 21n + 1}, since there are only 2n literal vertices, there must be n literal vertices with sum 8, while the other n must have sum 11. Note that having σ(v l ) = 8 for some literal vertex v l requires the three incident formula edges to be assigned label 1, and similarly for the edge v l v l . In other words, if σ(v l ) = 8 for some literal l, then ℓ(v l v l ) = 1, which forces to have σ(v l ) > 8 so that σ(v l ) ≠ σ(v l ), and thus we must have σ(v l ) = 11, which requires the three formula edges incident to v l to be assigned label 2. ◇

We can now prove that we have the desired equivalence between 1-in-3 satisfying Φ (and thus F and F ), and designing an equiproper 2-labelling of G. It follows from the following arguments:

• Imagine that having ℓ(v C v l ) = 2 for some clause C and some literal l by some equiproper 2-labelling ℓ of G models that l brings truth value true to C by some truth assignment to the variables of Φ, and that having ℓ(v C v l ) = 1 models that l brings truth value false to C.

• The fact that, for any clause vertex v C , exactly one incident formula edge must be assigned label 2 while the other two must be assigned label 1 (Claim 3.5), models that C is considered satisfied by a truth assignment only if it contains one true literal and two false ones.

• Likewise, the fact that, for any literal vertex v l , all incident formula edges must be assigned the same label, and that this label must be different from that assigned to the three formula edges incident to v l (Claim 3.5), models that each of v l and v l brings, by any truth assignment, the same truth value to all clauses that contain them, and l and l are assigned opposite values.

From these arguments, it is not too complicated to see that the equivalence holds. Particularly, the fact that an equiproper 2-labelling of G can be designed from any truth assignment 1-in-3 satisfying Φ follows from the labelling arguments given through Claims 3.2 to 3.5.

Looking closely at the reduction in the proof of Theorem 3.1, it can be observed that the reduced graph G we construct always verifies χ Σ (G) = 2. This is because G is almost locally irregular (and thus very close to have χ Σ (G) = 1), in the sense that an edge uv of G verifies d(u) = d(v) if and only if {u, v} is a pair of opposite literal vertices {v x , v x }. Indeed, note that all a i 's have degree 15 or 20, all b i 's have degree 6, all c i 's have degree 8, all clause vertices have degree 15, all literal vertices have degree 7, all d i 's have degree 44, all e i 's have degree 22, all f i 's have degree 3, and all p i 's, q i 's, and r i 's have degree at most 3. A proper 2-labelling of G can then be obtained by considering every positive literal vertex v x , assigning label 1 to any one formula edge incident to v x , and eventually assigning label 2 to all other edges of G. As a result, all a i 's have sum 30 or 40, all b i 's have sum 12, all c i 's have sum 16, all clause vertices have sum in {27, 28, 29, 30}, all positive literal vertices have sum 13, all negative literal vertices have sum 14, all d i 's have sum 88, all e i 's have sum 44, all f i 's have sum 6, and all p i 's, q i 's, and r i 's have sum at most 6. Particularly, recall that for every non-isolated set {p i , q i , r i }, the only possible edge joining its vertices is q i r i (which might have been added when dealing with case ★), in which case d(q i ) = 1 and d(r i ) = 2, and thus σ(q i ) = 2 and σ(r i ) = 4. Meanwhile, if {p i , q i , r i } is isolated, then p i r i and q i r i are edges, but we have d(p i ) = d(q i ) = 1 and d(r i ) = 2, and thus σ(p i ) = σ(q i ) = 2 and σ(r i ) = 4.

This implies a stronger result, being that even under the assumption that some graph G admits proper 2-labellings, deciding whether G admits equiproper 2-labellings is not easy, unless P=NP.

General upper bounds

In this section, we focus on proving upper bounds on χ Σ (G) when G lies in general graph classes. By Observation 2.1, recall that we always have χ Σ (G) ≤ s(G), and thus first bounds can already be deduced from known ones on the irregularity strength. Particularly, recall that we always have s(G) ≤ |V (G)| -1 (see [START_REF] Nierhoff | A tight bound on the irregularity strength of graphs[END_REF]), and the improved bound s(G) ≤ 6 ⌈ |V (G)| δ(G) ⌉ (see [START_REF] Kalkowski | A new upper bound for the irregularity strength of graphs[END_REF]) when δ(G) is large enough. The latter bound also shows that, like the irregularity strength, pathological graphs for our problem (as those from Observation 2.2) must involve vertices of small degree.

Our main goal in this section is to provide upper bounds, for particular graphs G, that sort of lie in between |V (G)| 2 (theoretical lower bound from Observation 2.2) and |V (G)| (upper bound from [START_REF] Nierhoff | A tight bound on the irregularity strength of graphs[END_REF]). In that spirit, the two bounds we provide are about 3|V (G)|

4

. The proofs we provide, in particular the one of upcoming Theorem 4.2, draw direct inspiration from [START_REF] Kalkowski | A new upper bound for the irregularity strength of graphs[END_REF], combined with new ideas to be exposed below. As emphasised by Observation 2.2, 1-vertices are, again, a great source of trouble, which explains why our most general result, Theorem 4.2 for connected graphs of minimum degree at least 4, requires vertices of sufficiently large degree. To also make a step towards such pathological graphs as well, we also consider trees, in Theorem 4.1.

As mentioned earlier, irregular labellings are always equiproper, the reason being that, by such labellings, the resulting σ has a very strong property, being that every resulting sum appears exactly once. Generally speaking, when designing an equiproper labelling, having sums appearing lots of times is rather tricky, as it forces all resulting sums to appear lots of times too (though it can be done in very particular contexts, recall the proof of Theorem 2.6).

There is a convenient intermediate case, however, being that if, by a proper labelling, all resulting sums appear at most twice, then the labelling is equiproper. Clearly, such a property is much weaker than being irregular, so one can expect it to be easier to work with. Consequently, we come up with the following notions. A k-vertex-colouring of a graph is strongly equitable if, for every i ∈ {1, . . . , k}, we have nb(i) ≤ 2. Now, we say that a labelling ℓ of a graph is loosely irregular if ℓ is proper and, for every i ∈ N + such that nb(i) ≠ 0, we have nb(i) ∈ {1, 2}. As loosely irregular labellings might make this presumption believable. Another direction could be to investigate the existence of graphs that are worse than stars for equiproper labellings.

• It is important to note, however, that if one aims at deducing the exact value of χ Σ (G) for some graph G, then one sometimes has to consider labellings where all resulting sums appear a lot. This is well illustrated by the proof of Theorem 2.6. However, the structure of paths and cycles is so regular that it is not clear whether this phenomenon is frequent in general or not. To progress towards this question, maybe it could be interesting to investigate locally irregular graphs. Recall indeed that if G is locally irregular, then χ Σ (G) = 1. However, depending on the degree sequence of G, it is not clear what χ Σ (G) should be in general: intuitively, if the degree sequence of G is sort of balanced (all degree values appear about the same number of times) then χ Σ (G) should be close to 1, while, if the degree sequence is unbalanced (all degree values appear different numbers of times, and the degree values are pairwise close) then it is more likely that χ Σ (G) should be large. In some sense, such examples could be among the most pathological ones (while being representative of all graphs), and it could thus be of prime interest to understand them fully. Recall en passant that nice stars (which we considered in Observation 2.2) are locally irregular.

• Towards improving Theorems 4.1 and 4.2, it could be crucial to develop new labelling methods. Note that, when dealing with proper labellings, one important method is the modulo method, used e.g. in [START_REF] Karoński | Edge weights and vertex colours[END_REF], through which, by a labelling, we ask adjacent vertices to have distinct sums modulo some fixed value. In the case of equiproper labellings, this method is not quite viable in general, as, through the modulo method, we somewhat do not pay attention to the actual vertex sums, which are crucial in our definition of equitability. Our proofs of Theorems 4.1 and 4.2, however, showcase safe situations in which restricting the sums to some modulo can be done. So we wonder whether we can go farther with this approach, especially since it has been used for irregular labellings (see e.g. [START_REF] Nierhoff | A tight bound on the irregularity strength of graphs[END_REF]).

• Regarding our complexity result in Section 3, Theorem 3.1, note that, in our reduction, the reduced graph is not connected in general, so one first question could be on modifying our proof so that the result holds for connected graphs. One could also wonder about establishing the same result for graphs with additional properties, such as being bipartite. Indeed, recall that deciding whether χ Σ (G) ≤ 2 for a given graph G is NP-complete in general [START_REF] Dudek | On the complexity of vertex-coloring edge-weightings[END_REF], but polynomial-time solvable when G is bipartite [START_REF] Thomassen | The 3-flow conjecture, factors modulo k, and the 1-2-3conjecture[END_REF]. Thus, restricting Theorem 3.1 to bipartite graphs would draw a neat difference between proper labellings and equiproper labellings. Similarly, note that some numbers in the proof of Theorem 3.1 are voluntarily large to make the arguments clearer, but, through optimising them and coming up with new structures, maybe it could be possible to establish a similar result for e.g. graphs of bounded degree (note that deciding whether χ Σ (G) ≤ 2 holds for a given cubic graph G is NP-complete [START_REF] Ahadi | Algorithmic complexity of proper labeling problems[END_REF]). Another question could be about generalising Theorem 3.1 to equiproper k-labellings: that is, for any fixed k ≥ 2, we wonder whether deciding if χ Σ (G) ≤ k is NP-complete. Note that we proved this for k = 2. A last question could be about the complexity of determining s(G) for a given graph G, which is still unknown, and was recently investigated in [START_REF] Bensmail | On the hardness of determining the irregularity strength of graphs[END_REF].

5 Figure 1 :

 51 Figure 1: Cases for cycles in the proof of Theorem 2.6. Numbers in vertices are sums obtained by the depicted equiproper 3-labelling. In each case, vertex v 0 is filled with gray.

  and σ(v n-2 ) = 5. Then, nb(3) = nb(5), while nb(2) = nb(4) = nb(6), and nb(3) = nb(2) + 1.

  and σ(v n-3 ) = 4. Then, nb(3) = nb(4) = nb(5), while nb(2) = nb(6), and nb(3) = nb(2) + 1. Also all vertices of G have sum in {2, 3, 4, 5, 6} and no two edges at distance 2 are assigned the same label. Then, the resulting 3-labelling of G is equiproper.

Figure 2 :

 2 Figure 2: Part of the reduction in the proof of Theorem 3.1. Red edges are 1-edges, while blue edges are 2-edges.Numbers near 1-edges and 2-edges incident to some vertex indicate how many 1-edges and 2-edges are incident to that vertex. For legibility reason, note that not all edges are drawn. Particularly, in this illustration, the 1-edges and 2-edges incident to p 1 , q 1 , and r 1 depict the case where we must add at least two 1-edges and at least two 2-edges incident to the d i 's and e i 's. On the other hand, there are no 1-edges and 2-edges incident to p 21n+1 , q 21n+1 , and r 21n+1 , which corresponds to the case where no 1-edges and 2-edges miss.

21n 2 <

 2 39 and 19 < 200n21n 2

  ) ≥ 19n, nb(8) ≥ 20n, nb(11) ≥ 20n, nb(44) = 21n, nb(1) ≥ 21n, nb(2) ≥ 21n, and nb(3) ≥ 21n.

  • If |E(G)| ≡ 4 mod 5 (with |E(G)| ≥ 9), then we consider every i ∈ {0, . . . , n -5}, and as previously assign label 1 to e i if i ≡ 0, 1 mod 5, label 2 to e i if i ≡ 2 mod 5, and label 3 to e i otherwise, if i ≡ 3, 4 mod 5. Finally, we assign label 1 to e n-4 and e n-3 , label 2 to e n-2 , and label 3 to e n-1 . Then, for every i ∈ {1, . . . , n -5}, we get σ(

•

  Start from G Φ , the graph modelling Φ, having 2n clause vertices v C1 , . . . , v Cn , v C1 , . . . , v Cn associated to C 1 , . . . , C n , C 1 , . . . , C n , and 2n literal vertices v x1 , . . . , v xn , v x1 , . . . , v xn associated to x 1 , . . . , x n , x 1 , . . . , x n . Also, G Φ has formula edges as indicated by F and F . More precisely, note that G is, for now, the (cubic) disjoint union of G F and G F . • Now, add to the graph 18n new vertices a 1 , . . . , a 18n , isolated for now. Similarly, add 20n new vertices b 1 , . . . , b 20n , and 20n new vertices c 1 , . . . , c 20n . Last, add 21n 2 new vertices d 1 , . . . , d 21n

	(recall n is even) to the graph, and 21n 2 new vertices e 1 , . . . , e 21n 2 .	2

It can be observed that s(G) and χ Σ (G) are well defined if and only if G does not contain K

, the complete graph on two vertices, as a connected component. We say G is nice whenever it has this property.[START_REF] Baudon | Equitable neighbour-sum-distinguishing edge and total colourings[END_REF] This notion was introduced by Meyer in[START_REF] Meyer | Equitable coloring[END_REF]; we voluntarily do not survey the topic in the current work, as this is not required at any point of our investigations.

Throughout, a k-vertex refers to a vertex of degree k.

A graph is locally irregular if every two of its adjacent vertices have different degrees.

Acknowledgement

The problem investigated in this work was suggested by Éric Sopena, whom we thank.

mentioned earlier, a loosely irregular labelling is always equiproper, as, by such a labelling, the vertex-colouring (induced by the sums) is proper and strongly equitable.

We are now ready to prove our two results in this section. We start off with trees.

Theorem 4.1. If T is a nice tree on n ≥ 9 vertices, then χ Σ (T ) ≤ 3 ⌈ n 4 ⌉. Proof. Consider a vertex r of T with maximum degree ∆(T ) = ∆ ≥ 2. We may even assume ∆ ≥ 3 as otherwise T would be a path, and the result would follow from Theorem 2.6. Thus, let us denote by u 1 , u 2 , and u 3 any three neighbours of r. We consider that T is rooted at r, which, in the usual way, defines a virtual orientation of T from its root to its leaves, by which every non-root vertex is incident to a unique parent edge (going to its unique neighbour closer to r). For every vertex of T , all its incident edges (if any) that are not its parent edge (if its exists) are its child edges.

Let now ϕ be a strongly equitable proper {1, . . . , 2 ⌈ n 4 ⌉}-vertex-colouring of T -r, with the additional property that ϕ(u 1 ) = 2 ⌈ n 4 ⌉ -2, ϕ(u 2 ) = 2 ⌈ n 4 ⌉ -1, and ϕ(u 3 ) = 2 ⌈ n 4 ⌉. Since n ≥ 9, note that ϕ assigns at least six different colours. To obtain such a vertex-colouring, one can, e.g., just process the vertices of T -r as they are encountered during a BFS algorithm performed from r, starting with considering u 1 , u 2 , and u 3 first (assigning them the desired colours), and, whenever considering a new vertex v, assigning any colour different from that assigned to its parent u, and that has not already been assigned twice. Particularly, it can be noted that we always have

which means that, when treating v, at least one colour α assigned at most once is available.

If that colour α is not the same as that assigned to u, then we can freely assign colour α to v and go on. Otherwise, if u is assigned colour α, then we can consider any other colour β / ∈ {2 ⌈ n 4 ⌉ -2, 2 ⌈ n 4 ⌉ -1, 2 ⌈ n 4 ⌉} assigned by ϕ (recall there at at least six colours), and swap all assigned α's and β's. As a result, v can now be assigned colour α, and the process can go on. Particularly, note that swapping colours the way we do preserves that the colours of u 1 , u 2 , and u 3 are pairwise distinct. So, eventually, if we have ϕ(u 1 ) ≠ 2 ⌈ n 4 ⌉ -2, ϕ(u 2 ) ≠ 2 ⌈ n 4 ⌉ -1, or ϕ(u 3 ) ≠ 2 ⌈ n 4 ⌉, then, by swapping pairs of colours, we can guarantee ϕ(u 1 ) = 2 ⌈ n 4 ⌉ -2, ϕ(u 2 ) = 2 ⌈ n 4 ⌉ -1, and ϕ(u 3 ) = 2 ⌈ n 4 ⌉. We start by designing a (3 ⌈ n 4 ⌉)-labelling ℓ of T such that, for every vertex v ∈ V (T ) ∖ {r}, we have σ(v) ≡ ϕ(v) mod 3 ⌈ n 4 ⌉. For that, we proceed as follows. We start from all edges of T being unlabelled. We then repeatedly consider one vertex v whose all incident child edges are labelled by ℓ, while its incident parent edge vu is not, and assign a label to vu by ℓ so that σ(v) fulfils the desired condition. Precisely, we choose ℓ(vu) in the following way. We look at the sum of the labels assigned to the child edges incident to v, and, denoting by x the value of this sum, we assign to vu a label y in {1, . . . , 3 ⌈ n 4 ⌉} so that x + y ≡ ϕ(v) mod 3 ⌈ n 4 ⌉. Note that this is always possible, since we are working modulo 3 ⌈ n 4 ⌉ and assign labels in {1, . . . , 3 ⌈ n 4 ⌉}. Note that this process does go through all vertices of T -r since T is 1-degenerate (in particular, we can start with any leaf as v), and, once all vertices have been treated, all edges of T are assigned a label by ℓ. Also, we have σ(v) ≡ ϕ(v) mod 3 ⌈ n 4 ⌉ for every v ∈ V (T ) ∖ {r}. As a general remark, note also that it is always possible to alter ℓ(ru 1 ), ℓ(ru 2 ), and ℓ(ru 3 ) so that σ(u

, respectively, and this can be achieved by either adding ⌈ n 4 ⌉ to some label, or subtracting 2 ⌈ n 4 ⌉ from it. Formally, regarding ru 1 (the process is identical regarding ru 2 and ru 3 ), if ℓ(ru 1 ) < 2 ⌈ n 4 ⌉ + 1, then we reach the desired condition upon adding ⌈ n 4 ⌉ to ℓ(ru 1 ), while, if ℓ(ru 1 ) ≥ 2 ⌈ n 4 ⌉ + 1, then we reach those conclusions upon subtracting 2 ⌈ n 4 ⌉ from ℓ(ru 1 ). Applying such alteration to some ru i is called performing a valid change to ru i . By the above, we either add ⌈ n 4 ⌉ to ℓ(ru i ), in which case the valid change is said increasing, or subtract 2 ⌈ n 4 ⌉ from ℓ(ru i ), in which case it is said decreasing. Back to considering ℓ, if the resulting sum function σ is proper and strongly equitable, then ℓ is equiproper and we are done. Otherwise, it must be that either 1) ℓ is not proper because of r (which requires that σ(r) mod 3

We consider these two cases in what follows, and perform fixing modifications on ℓ in each.

• Assume first ℓ is not proper. We consider four cases.

σ(r) mod 3 ⌈ n 4 ⌉ belongs to {⌈ n 4 ⌉ + 1, . . . , 2 ⌈ n 4 ⌉ -3}. In this case, recall that σ(r) mod 3 ⌈ n 4 ⌉ ≠ σ(u 1 ) mod 3 ⌈ n 4 ⌉. Then, by performing a valid change to ru 1 , we get that only r and u 1 have sum in {2 ⌈ n 4 ⌉ + 1, . . . , 3 ⌈ n 4 ⌉ -1, 0} modulo 3 ⌈ n 4 ⌉. Also, we still have σ(r) ≠ σ(u 1 ). Thus, the labelling is equiproper. σ(r) mod 3 ⌈ n 4 ⌉ belongs to {1, . . . , ⌈ n 4 ⌉ -3}. It must be that, w.l.o.g., either we can perform an increasing valid change to both ru 1 and ru 2 , or we can perform a decreasing valid change to both ru 1 and ru 2 . Perform these two valid changes. As a result, only r, u 1 , and

4 ⌉, while we still have σ(u 1 ) ≠ σ(u 2 ) (which is even true modulo ⌈ n 4 ⌉), and σ(r) / ∈ {σ(u 1 ), σ(u 2 )} (which is also true modulo ⌈ n 4 ⌉). Thus, the labelling is equiproper.

, the same sum as some u i . Then just apply a valid change to any ru j with j ≠ i. Then, only r and u j have sum in {2 ⌈ n 4 ⌉+1, . . . , 3 ⌈ n 4 ⌉-1, 0} modulo 3 ⌈ n 4 ⌉, while we still have σ(r) ≠ σ(u j ) (since this is still true modulo ⌈ n 4 ⌉). Then the resulting labelling is equiproper.

Again, let i ∈ {1, 2, 3} be the unique index such that, modulo ⌈ n 4 ⌉, we have σ(r) = σ(u i ). Then, apply the valid changes to both ru j and ru k , where {j, k} = {1, 2, 3} ∖ {i}. Note that, regardless of whether these two valid changes are both increasing or decreasing, or whether they are of different types, we get that r, u j , and u k are the only vertices with sum in {2 ⌈ n 4 ⌉ + 1, . . . , 3 ⌈ n 4 ⌉ -1, 0} modulo 3 ⌈ n 4 ⌉. Also, we still have σ(u j ) ≠ σ(u k ) (this even holds modulo ⌈ n 4 ⌉) and σ(r) / ∈ {σ(u j ), σ(u k )} (again, this is true modulo ⌈ n 4 ⌉). Thus, the attained labelling is equiproper.

• Assume now ℓ is proper but nb(σ(r)) > 2. We here consider three cases.

σ(r) mod

Proof. Let v 1 , . . . , v n be an ordering over the vertices of G. According to this ordering, every edge v i v j with i < j is forward from v i 's point of view, while it is backward from v j 's one. Among all possible orderings as v 1 , . . . , v n , we fix one such that every v i with i ∈ {1, . . . , n -1} is incident to forward edges. Such an ordering can be obtained e.g. by choosing any vertex as v n , and then reversing the ordering in which vertices are encountered during a BFS algorithm from v n .

Set

To design an equiproper (3 ⌈ n 4 ⌉ + 2)-labelling of G, we actually design a loosely irregular one, ℓ, through the following ideas, starting from all edges unlabelled. We treat the v i 's one by one in order, starting from v 1 and finishing with v n-1 (eventually, v n will be treated separately). Whenever we consider a new v i this way, we assume v i is incident to b ≥ 0 backward edges e 1 , . . . , e b and f ≥ 1 forward edges f 1 , . . . , f f . We denote by u 1 , . . . , u b and w 1 , . . . , w f the ends of e 1 , . . . , e b and f 1 , . . . , f f , respectively, different from v i . We assume the e i 's and f i 's are ordered so that their ends follow the ordering v 1 , . . . , v n . By that, we mean that if

When dealing with v i , we will modify labels assigned by ℓ to edges incident to v i so that we reach a suitable situation at v i , i.e., a situation fulfilling the following properties:

1. For every j ≤ i, all edges incident to v j have been assigned a label in {1, . . . , 3

For every j < i, all forward edges incident to v j not incident to v i are assigned labels in

For every forward edge

For every two adjacent vertices v j and v j ′ with j, j ′ ≤ i (and thus j ≠ j ′ ), we have ϕ(v j ) ≠ ϕ(v j ′ ), and, thus,

6. For every pair P = (x, x + ⌈ n 4 ⌉) ∈ P, there are at most two v j with j ≤ i such that Φ(v j ) = P .

Having two possible values (modulo 2 ⌈ n 4 ⌉), those in Φ(v i ), for any σ(v i ) all along the process guarantees that, later on, when treating a later vertex v j adjacent to v i , we can locally alter the labelling to modify σ(v j ) (and thus potentially reach more pairs as Φ(v j )) without breaking it is loosely irregular. Note indeed that, by Properties 3 and 4, when treating v j , we can always perform a valid change on v j v i , i.e., either increase ℓ(v

, respectively, while preserving Property 1. Property 5 is to ensure ℓ is proper at any point, while Property 6 is to guarantee σ ℓ is strongly equitable.

So, the tricky part, when treating a new v i , is to perform local changes (valid changes backwards, and properly choosing labels assigned to the forward edges) so that a suitable situation is attained. The upcoming claims prove formally how to handle the main possible cases. Let us add that these claims can only be proved under the assumption that vertices have large enough degrees, i.e., at least 4; in particular, from the arguments given in the proofs of Claims 4.3 to 4.5, one can retrieve why we need our hypothesis on δ(G).

The first claim corresponds to situations where v i has no backward neighbours.

Claim 4.3. If b = 0, then, since δ(G) ≥ 4, through performing changes around v i complying with the properties of a suitable situation, a suitable situation at v i can be reached.

Proof of the claim. Since b = 0, Properties 1, 2, and 5 do not have to be considered when dealing with v i . Through assigning any label in {1, . . . , 2 ⌈ n 4 ⌉} to f 1 and any label in {⌈ n 4 ⌉ + 1, . . . , 2 ⌈ n 4 ⌉} to f 2 , . . . , f f , we meet Property 3 of a suitable situation at v i . Also, when assigning such labels, as long as we define Φ(v i ) so that the resulting σ(v i ) is ϕ(v i ) (the lowest value in Φ(v i )), we also meet Property 4. So the main matter is choosing Φ(v i ) so that Property 6 holds.

By assigning labels to f 1 , . . . , f f as mentioned above, note that σ(v i ) can take any value in which are, thus, possible values we could consider as ϕ(v i ). Recall however that ϕ(v i ) must belong to {1, . . . ,

and, thus, at least

values in S must belong to {1, . . . , ⌈ n 4 ⌉} modulo 2 ⌈ n 4 ⌉, and are thus values we could choose as ϕ(v i ). Now, regarding Property 6, since f ≥ 4 (due to δ(G) ≥ 4), this is at least 2 ⌈ n 4 ⌉ possible values since n ≥ 9 (which guarantees ⌊5 -3

we deduce there is some value in S that appears as ϕ(v j ) for at most one v j with j < i. We can then assign labels to the f j 's and define Φ(v i ) accordingly, to reach a suitable situation at v i . ◇

We now deal with situations where v i has backward neighbours. To make the analysis clearer, we start with the "surrounding" of v i being in initial position. By that, we mean we apply the following local changes:

• for every j ∈ {1, . . . , b}, if σ(u j ) = ϕ ′ (u j ), then we perform a (decreasing) valid change onto v i u j , so that σ(u j ) = ϕ(u j ) (modulo 2 ⌈ n 4 ⌉); • we set ℓ(f 1 ) = 1;

• for every j ∈ {2, . . . , f }, we set ℓ(f j ) = ⌈ n 4 ⌉ + 1. In other words, we make σ(v i ) as small as possible through performing valid changes backwards, and, for the forward edges, assigning the smallest labels possible complying with Properties 3 and 4. Note that Φ(v i ) being not defined yet, Property 4 is technically not fully fulfilled yet.

Then, since δ(G) ≥ 4, through performing changes around v i complying with the properties of a suitable situation, a suitable situation at v i can be reached.

Proof of the claim. Recall that, currently, ℓ(f 1 ) = 1. For every x ∈ {(2α+2) ⌈ n 4 ⌉+1, . . . , (2α+3) ⌈ n 4 ⌉}, note that we can increase ℓ(f 1 ) by at most 2 ⌈ n 4 ⌉ -1 (thus so that ℓ(f 1 ) is no more than 2 ⌈ n 4 ⌉) so that σ(v i ) = x while (x, x + ⌈ n 4 ⌉) lies in P and is, thus, a possible pair we could define a Φ(v i ). This is thus a set of ⌈ n 4 ⌉ possible pairs as Φ(v i ). Note then that, upon performing a pair of valid changes backwards (which are increasing, since we started in initial position), we increase σ(v i ) by 2 ⌈ n 4 ⌉, which allows, through the same arguments, to reach ⌈ n 4 ⌉ other possible pairs as Φ(v i ) (see Figure 3). By performing pairs of valid changes backwards this way, we thus deduce a set of

possible pairs as Φ(v i ), which can be reached through local changes that fulfil Properties 1 to 4 of a suitable situation. It now remains to prove that the last part of the statement holds, i.e., that at least one of these pairs can be chosen as Φ(v i ) so that Properties 5 and 6 also hold. Since δ(G) ≥ 4, we have b + f ≥ 4. Note that at most

of the possible pairs are forbidden as Φ(v i ) due to Properties 5 and 6. Thus, one of the pairs can be chosen as Φ(v i ) if b ≥ 6, and we can change labels around v i accordingly to be done in this case.

For smaller values of b, below we refine the analysis to prove we can also be done.

In particular, ideas we use include the following. Above, note that we first alter ℓ(f 1 ) so that σ(v i ) reaches a value x in {1, . . . , ⌈ n 4 ⌉} modulo 2 ⌈ n 4 ⌉, and this can be done so that ℓ(f 1 ) reaches value at most 2 ⌈ n 4 ⌉ (one of our constraints). To then open up to more pairs as (ϕ(v i ), ϕ(v i ) + ⌈ n 4 ⌉), we then perform, from any of these possible values x, valid changes in pairs, to repeatedly increase ϕ(v i ) by an additional 2 ⌈ n 4 ⌉, thereby getting new pairs to reach and exploit as Φ(v i ). So, in some sense, some valid change is not exploited when b is odd. To overcome this issue, we somewhat pair it with an additional virtual valid change, which is simulated by adding another ⌈ n 4 ⌉ to ℓ(f 1 ). In particular, see below, this can be done so that ℓ(f 1 ) retains a desired value.

• If b ∈ {4, 5}, then the number of possible pairs we can consider as Φ(v i ) is at least 3 ⌈ n 4 ⌉. Since n ≥ 17 and b ∈ {4, 5}, the number of forbidden pairs is thus strictly less than 3 ⌈ n 4 ⌉, and there is thus one we can choose as Φ(v i ), and perform the corresponding local label changes.

• If b = 3, then the number of possible pairs we can consider as Φ(v i ) is at least 2 ⌈ n 4 ⌉. Meanwhile, as mentioned above, the number of forbidden pairs as

which is at most 2 ⌈ n 4 ⌉ (particularly, equality holds whenever n ≡ 0, 3 mod 4). In this case, it suffices to show that there is one additional pair we could choose as Φ(v i ). From the initial position, start by adding some value x ∈ {1, . . . , ⌈ n 4 ⌉} to ℓ(f 1 ) so that σ(v i ) ≡ 1 mod 2 ⌈ n 4 ⌉. Then, apply the three valid changes backwards, before adding another ⌈ n 4 ⌉ to ℓ(f 1 ) (which, as described above, is intended to simulate a last valid change). As a result, σ(v i ) ≡ 1 mod 2 ⌈ n 4 ⌉, and the pair (σ(v i ), σ(v i ) + ⌈ n 4 ⌉) does not belong to the set of pairs of P we have considered earlier on (since it was obtained, essentially, by virtually performing an additional pair of valid changes). So we have found an additional pair as desired, and we can make local label changes so that a suitable situation is reached at v i . Particularly, note that ℓ(f 1 ) ≤ 2 ⌈ n 4 ⌉ + 1, which complies with Property 4.

• If b = 2, then the number of possible pairs as Φ(v i ) is at least 2 ⌈ n 4 ⌉. Since δ(G) ≥ 4, we thus have f ≥ 2. The number of forbidden pairs in this case is thus at most

In that case, note that by increasing ℓ(f 2 ) by ⌈ n 4 ⌉, we get ℓ(f 2 ) = 2 ⌈ n 4 ⌉+1, which still complies with Property 3, and has the same effect as performing another valid change backwards. We can thus proceed similarly as in the previous case to reach another possible pair as Φ(v i ), and thus we can attain a suitable situation at v i .

• If b = 1, then f ≥ 3. In this situation, note that, upon adding adding 1 and ⌈ n 4 ⌉-1 to ℓ(f 2 ) and ℓ(f 3 ), respectively, we still have that Property 3 holds, and σ(v i ) increases by ⌈ n 4 ⌉, which has the same effect as performing a valid change backwards. This means the number of possible pairs we can consider as Φ(v i ) is actually at least 2 ⌈ n 4 ⌉. Meanwhile, the number of forbidden pairs here is at most So, again, we can perform label changes around v i so that we reach a suitable situation.

This concludes the proof of the claim. ◇ Claim 4.5. Assume b ≥ 1, and, in initial position, we currently have σ(v i ) = 2α ⌈ n 4 ⌉ + β for some α ≥ 0 and β ∈ {1, . . . , ⌈ n 4 ⌉} (i.e., σ(v i ) mod 2 ⌈ n 4 ⌉ ∈ {1, . . . , ⌈ n 4 ⌉}). Then, since δ(G) ≥ 4, through performing changes around v i complying with the properties of a suitable situation, a suitable situation at v i can be reached.

Proof of the claim. For every x ∈ {2α ⌈ n 4 ⌉ + β, . . . , (2α + 1) ⌈ n 4 ⌉}, note that we can increase ℓ(f 1 ) by some value in {0, . . . , ⌈ n 4 ⌉ -β} (thus so that ℓ(f 1 ) remains at most 2 ⌈ n 4 ⌉) so that the resulting σ(v i ) lies in {1, . . . , ⌈ n 4 ⌉} modulo 2 ⌈ n 4 ⌉. Then, (x, x + ⌈ n 4 ⌉) ∈ P is a possible pair we could consider as Φ(v i ), and we thus deduce a set of ⌈ n 4 ⌉ -β + 1 first possible pairs as Φ(v i ). Note also that by performing two valid changes backwards (thus increasing), we get σ(v i ) = 2(α + 2) ⌈ n 4 ⌉ + β, and the same arguments apply. This also applies upon performing pairs of valid changes backwards. Thus, so far, we deduce a set of

possible pairs of P that could be considered as Φ(v i ). Also (see Figure 4), from the initial position, by increasing ℓ(f 1 ) by at most ⌈ n 4 ⌉ -β + 1 (thus maintaining ℓ(f 1 ) ≤ ⌈ n 4 ⌉ + 1) we can have σ(v i ) reach value (2α + 1) ⌈ n 4 ⌉ + 1. By then performing one valid change backwards, and then increasing ℓ(f 1 ) again by at most β -1, we get access, as Φ(v i ), to all pairs of P with ϕ(v i ) ∈ {(2α + 2) ⌈ n 4 ⌉ + 1, . . . , (2α + 2) ⌈ n 4 ⌉ + β -1}, thus to β -1 pairs. Again, this generalises upon performing pairs of valid changes backwards. We thus deduce another set of

other possible pairs as Φ(v i ). Thus, so far, we have a set of at least

pairs we could consider as Φ(v i ). Now, similarly as in the proof of Claim 4.4, the number of forbidden pairs as

Thus, if b ≥ 7, then one of the aforementioned pairs can be chosen as Φ(v i ), and by performing the corresponding local label changes, we are done. We now deal with the remaining values of b.

• If b ∈ {5, 6}, then the number of possible pairs as Φ(v i ) above is at least 3 ⌈ n 4 ⌉. Since n ≥ 17 and b ∈ {5, 6}, the number of forbidden pairs is strictly less than 3 ⌈ n 4 ⌉, and there is thus one pair we can choose as Φ(v i ) and make the corresponding local label changes around v i .

• If b = 4, then the number of possible pairs as

and thus

If this difference is 1, then there is a pair we can choose as Φ(v i ) and we are done. Now, since b = 4, by (1) above we note that there are ⌈ n 4 ⌉ -β + 1 extra pairs we could consider as Φ(v i ). Particularly, since β ≤ ⌈ n 4 ⌉, there is at least one extra pair we can consider, and so we are also done if the difference above is 0. So the last case is when the difference above is -1 (which occurs whenever n ≡ 0 mod 4), and we have β = ⌈ n 4 ⌉ (as otherwise, by (1), there would be at least two extra pairs we could consider as Φ(v i ), and we would be done). Here, we thus need to expose one extra pair that can be considered as Φ(v i ).

In this situation, consider the following label modifications, starting from the initial position. Start by adding 1 to ℓ(f 1 ) so that ℓ(f 1 ) = 2 and σ(v i ) ≡ ⌈ n 4 ⌉ + 1 mod 2 ⌈ n 4 ⌉. Now perform the four valid changes backwards, and increase ℓ(f 1 ) by another ⌈ n 4 ⌉. As a result, we have ℓ(f 1 ) = ⌈ n 4 ⌉ + 2, and σ(v i ) ≡ 1 mod 2 ⌈ n 4 ⌉. Particularly, we have (σ(v i ), σ(v i ) + ⌈ n 4 ⌉) ∈ P, and this pair is not part of those we have exposed in (1) and ( 2) above. Thus, this is one more pair we can consider as Φ(v i ), and, together with the ones we have exposed earlier, there is one we can properly choose as Φ(v i ), and perform the corresponding label changes to reach a suitable situation at v i .

• If b = 3, then the number of possible pairs as Φ(v i ) is at least 2 ⌈ n 4 ⌉. As in the previous case, taking the forbidden pairs into account, the number of possible pairs we can actually consider is at least

Again, if this difference is 1, then we have our conclusion. So, we can assume the difference is 0 (which occurs when n ≡ 3, 0 mod 4), and we just need to show there is an extra pair, apart from those behind (1) and ( 2), that can be considered as Φ(v i ).

-If β < ⌈ n 4 ⌉, then we can reach such a pair as follows. First, from the initial position, add

Then, ℓ(f 1 ) ≤ ⌈ n 4 ⌉ at this point. Now, perform the three valid changes backwards, and add another 2 ⌈ n 4 ⌉ to ℓ(f 1 ). As a result, we have 2

)) ∈ P, and this pair is not one of those behind (1) and ( 2). -If β = ⌈ n 4 ⌉, then, from the initial position, perform the three valid changes backwards, and add 1+2 ⌈ n 4 ⌉ to ℓ(f 1 ). As a result, we have ℓ(

4 ⌉) ∈ P and this pair is not one of those we have exhibited earlier.

Thus, in both cases, we can define Φ(v i ) properly, and make the corresponding label changes to reach a suitable situation at v i .

• If b = 2, then f ≥ 2. Besides the ⌈ n 4 ⌉ possible pairs as Φ(v i ) mentioned through (1) and ( 2), note that we can also add ⌈ n 4 ⌉-β +2 to ℓ(f 1 ) (so that ℓ(f 1 ) is at most ⌈ n 4 ⌉+2), perform the two valid changes backwards, and increase ℓ(f 2 ) by ⌈ n 4 ⌉ -1 (so that ℓ(f 2 ) = 2 ⌈ n 4 ⌉). Note that this complies with the properties of a suitable situation. As a result, note that σ(v i ) ≡ 1 mod 2 ⌈ n 4 ⌉, and that, for every x ∈ {0, . . . , ⌈ n 4 ⌉ -1}, the pair (σ(v i ) + x, σ(v i ) + x + ⌈ n 4 ⌉) ∈ P is not one of the pairs we have exposed earlier. Thus, upon increasing ℓ(f 1 ) by at most 2 ⌈ n 4 ⌉ + 1, we can reach ⌈ n 4 ⌉ more possible pairs as Φ(v i ). Together with the pairs behind ( 1) and ( 2), we thus deduce a set of 2 ⌈ n 4 ⌉ possible pairs we could consider as Φ(v i ). Actually, since b = 2, note that this number of possible pairs is at least 2 ⌈ n 4 ⌉ + 1 due to (1) (there are an extra ⌈ n 4 ⌉ -β + 1 ≥ 1 pairs here). Meanwhile, the number of forbidden pairs is

there is thus at least one pair we can properly choose as Φ(v i ), and make the corresponding label changes to get the conclusion we desire.

• If b = 1, then f ≥ 3. As in the last case of the proof of Claim 4.4, note that, via adding 1 and ⌈ n 4 ⌉ -1 to ℓ(f 2 ) and ℓ(f 3 ), respectively, we can, essentially, simulate a valid change backwards. Remark also that this results in ℓ(f 2 ) = 2, and that we could increase ℓ(f 2 ) by another 2 ⌈ n 4 ⌉ while still having ℓ(f 2 ) fulfilling Property 3. From this, by the same arguments as in the previous case, we deduce a set of 2 ⌈ n 4 ⌉ pairs we can consider as Φ(v i ). Meanwhile, the number of forbidden pairs is

we again deduce that there is one pair we can properly set as Φ(v i ), and adjust the labels around v i accordingly to reach a suitable situation.

We are thus done in all cases. ◇ Back to the proof of Theorem 4.2, we start from all edges of G unlabelled. Then we go through all of v 1 , . . . , v n-1 one by one in order. For each v i considered this way, we first perform label modifications around v i , if needed, so that we get in initial position. Then, by one of Claims 4.3, 4.4, and 4.5 (depending on the local situation), we can always modify labels around v i so that a suitable situation at v i is attained, and the process can go on.

Once all v i 's have been treated this way, all edges of G have been assigned a label, and if the resulting ℓ is not loosely irregular, then it must be because of v n . Particularly, either 1) v n has the same sum as one of its neighbours (which we denote u 1 , . . . , u d , for some d ≥ 4, in what follows), or 2) σ(v n ) is the sum by ℓ of three vertices (including v n ) of G.

For each backward edge v n u i , recall that we can perform a valid change. For every i ∈ {1, . . . , d}, we perform a (decreasing) valid change on v n u i if σ(u i ) = ϕ ′ (u i ). This way, for every i ∈ {1, . . . , d}, we have σ(u i ) = ϕ(u i ). Recall also that for every x ∈ N + such that x mod 2 ⌈ n 4 ⌉ ∈ {1, . . . , ⌈ n 4 ⌉}, there are at most two u i with ϕ(u i ) = x.

As mentioned earlier, if ℓ is not loosely irregular, then it can be because of two reasons.

-If ℓ is not proper, then, w.l.o.g., we have σ(u 1 ) = σ(v n ). As mentioned earlier, at most one other u i can verify σ(u 1 ) = σ(u i ). Since d ≥ 4, we might thus assume σ(u 2 ) ≠ σ(u 1 ), w.l.o.g. Now just perform a valid change to v n u 2 . As a result, we now have

, and, among all u i 's, only u 2 has this property. However, we have σ(u 2 ) ≠ σ(v n ). Thus, the resulting ℓ is proper. It is also loosely irregular, since, in {v 1 , . . . , v n-1 }, at most two vertices can have sum σ

For these reasons, we indeed deduce at most two vertices of G have sum σ(u 1 ), and similarly at most two vertices of G have sum σ(v n ).

-If ℓ is proper but not loosely irregular, then there are three vertices in G with sum σ(v n ).

Particularly, no u i has the same sum as v n . Then just perform a valid change to v n u 1 . Since u 1 is the only vertex among the u i 's to have sum in {⌈ n 4 ⌉+1, . . . , 2 ⌈ n 4 ⌉-1, 0} modulo 2 ⌈ n 4 ⌉, the resulting labelling is proper. Also, since at most two vertices in {v 1 , . . . , v n-1 } can have sum σ(v n ) -⌈ n 4 ⌉ or σ(v n ), and, in the first place, there were two such vertices with sum σ(v n )-⌈ n 4 ⌉, we deduce that, now, v n is the only vertex with sum σ(v n ). Thus, the resulting labelling is loosely irregular.

Start by performing one valid change to v n u 1 ; two cases can occur:

-If the resulting labelling is not proper, then it must be because, for some u i , we have σ(v n ) = σ(u i ). By our choice of u 1 and u 2 , we have u i / ∈ {u 1 , u 2 }. In that case, perform another valid change, to v n u 2 . As a result, the attained labelling is proper, since only u 1 and u 2 have sum in {⌈ n 4 ⌉ + 1, . . . , 2 ⌈ n 4 ⌉ -1, 0} modulo 2 ⌈ n 4 ⌉. Meanwhile, at most two vertices in {v 1 , . . . , v n-1 } have sum σ(v n ) or σ(v n ) -⌈ n 4 ⌉, one of which is u i , whose sum is σ(v n ) -⌈ n 4 ⌉. Thus, there are at most two vertices with sum σ(v n ) in G, and the labelling is loosely irregular.

-If the resulting labelling is proper but not loosely irregular, then there must be two vertices in {v 1 , . . . , v n-1 } with sum σ(v n ), and these two vertices do not include any of u 1 , . . . , u d since otherwise we would fall into the previous case. Here, just perform another valid change, to v n u 2 . Since u 1 and u 2 cannot have sum σ(v n ) due to how we chose them, the labelling is proper. Also, since at most two vertices of G have sum σ(v n ) or σ(v n ) -⌈ n 4 ⌉ modulo 2 ⌈ n 4 ⌉, and these two vertices were assumed to actually have sum σ(v n ) -⌈ n 4 ⌉, we deduce that v n is the only vertex of G with sum σ(v n ). Thus, the labelling is loosely irregular.

We thus end up with a loosely irregular (thus equiproper) (3 ⌈ n 4 ⌉ + 2)-labelling of G.

Conclusion

In this work, we have introduced and investigated an equitable version of proper labellings, where the notion of equitability is with respect to the induced sums. As seen earlier, notably through Observation 2.1, equiproper labellings sort of lie in between proper labellings and irregular labellings. The exact connection between the three is not clear however, as, for particular graphs G, sometimes χ Σ (G) is closer to χ Σ (G), while in other cases χ Σ (G) is closer to s(G), and there are even cases where χ Σ (G) actually lies somewhere in between χ Σ (G) and s(G). From a more general point of view, the fact that χ Σ (G) should always be at most 3 (as hypothesised by the 1-2-3 Conjecture, which might have been proved in [START_REF] Keusch | A Solution to the 1-2-3 Conjecture[END_REF]), while χ Σ (G) is not bounded above by an absolute constant (recall Observation 2.2), tend to locate the parameter χ Σ closer to the irregularity strength.

Our results in this work lead us to a few questions and directions, which we think could be subject to further work on the topic. For instance:

• We suspect that the upper bounds on χ Σ we provided in Section 4, even if made more general, would not be best possible in general, and that a type of bound as indicated by Observation 2.2 would be more relevant. If we had to make some guess, then maybe, for every nice n-graph G, it might be plausible that χ Σ (G) ≤ ⌈ n 2 ⌉ + O(1) always holds. Note that the proof methods we used to prove Theorems 4.1 and 4.2 would tend to support such a bound. Particularly, the use we made of strongly equitable proper vertex-colourings and