Julien Bensmail

Hervé Hocquard

Pierre-Marie Marcille

Going Wide with the 1-2-3 Conjecture

Keywords: distinguishing labelling, 1-2-3 Conjecture, fixed radius

In the so-called 1-2-3 Conjecture, the question is, for any connected graph not isomorphic to K 2 , whether we can label its edges with 1, 2, 3 so that no two adjacent vertices are incident to the same sum of labels. Many aspects of this conjecture have been investigated over the last past years, related both to the conjecture itself and to variations of it. Such variations include different generalisations, such as generalisations to more general graph structures (digraphs, hypergraphs, etc.) and generalisations with stronger distinction requirements.

In this work, we introduce a new general problem, which holds essentially as a generalisation of the 1-2-3 Conjecture to a larger range. In this variant, a radius r ≥ 2 is fixed, and the main task, given a graph, is, if possible, to label its edges so that any two vertices at distance at most r are distinguished through their sums of labels assigned to their edges at distance at most r. We investigate several general aspects of this problem, in particular the importance of r and its influence on the smallest number of labels needed to label graphs. We also show connections between our general problem and several other notions of graph theory, from both the distinguishing labelling field (e.g. irregularity strength of graphs) and the more general chromatic theory field (e.g. chromatic index of graphs).

Introduction

In distinguishing labellings, the main goal is generally to label some elements of a given graph so that certain pairs of elements can be pairwise distinguished, accordingly to some parameter computed from the labelling. This general definition relies on several flexible parameters, and can thus give birth to many notions and problems of interest. As an illustration, let us bring the survey [START_REF] Gallian | A dynamic survey of graph labeling[END_REF] by Gallian to the attention of the interested reader, in which hundreds of labelling techniques, studied throughout the years, are reported.

In this work, we are mostly interested in notions and problems that revolve around the so-called irregularity strength of graphs, and around the whole subfield of distinguishing labellings that the introduction of this parameter has initiated. In this area, the central notions are the following ones. Let G be a graph. By a k-labelling of G, we mean an assignment : E(G) → {1, . . . , k} of labels to the edges of G. In connection with motivations first considered by Chartrand et al., for instance in [START_REF] Chartrand | Irregular networks[END_REF] (related to measures of regularity and irregularity in graphs), the main parameter of interest here, computed from , is the sum of labels incident to the vertices. That is, for every vertex v ∈ V (G), one can compute a colour c (v), which is defined as c (v) = u∈N (v) (vu). We say that is irregular if c is injective, i.e., no two vertices u and v of G verify c (u) = c (v). Assuming G admits irregular labellings, which is the case whenever G is nice, i.e., has no connected component isomorphic to K 2 (and at most one isolated vertex in this case), the notably by the fact that the problem of determining whether χ 1 Σ (G) ≤ 2 holds for a given nice graph G is NP-complete [START_REF] Dudek | On the complexity of vertex-coloring edge-weightings[END_REF]. Generally speaking, the conjecture was mostly verified for complete graphs and 3-colourable graphs [START_REF] Karoński | Edge weights and vertex colours[END_REF], but partial results also exist for other graph classes and variants of the problem (see [START_REF] Seamone | The 1-2-3 Conjecture and related problems: a survey[END_REF]).

This work is thus dedicated to introducing and studying r-proper labellings, for r ≥ 2. We start in Section 2 by showing existing connections between the parameters χ r Σ and other known parameters of graph theory, from which we will later be able to derive several results. Notably, exploiting one of these connections, we show, in Section 3, that the problem of determining χ r Σ (G) for a given r-nice graph G is NP-complete in general. In Sections 4 and 5, we then prove both lower and upper bounds on the parameters χ r Σ with r ≥ 2. In particular, we show that, for every r ≥ 2, there exist graphs G requiring up to O(2 r-1 ) distinct labels in their r-proper labellings, while every r-nice graph G admits such a labelling assigning O(∆(G) 2r-1 ) distinct labels. We conclude in Section 6 by discussing possible directions for further work on the topic.

Connections with other graph notions

In this section, we explore connections between r-proper labellings and some other graph notions. As one could expect, we establish several connections with other types of distinguishing labelling techniques. More intriguingly, we also show some connection with proper edge-colouring, thus with the more classical chromatic theory.

Proper labelling of hypergraphs

Attempts were made in [START_REF] Bennett | Weak and Strong Versions of the 1-2-3 Conjecture for Uniform Hypergraphs[END_REF][START_REF] Kalkowski | The 1-2-3-Conjecture for Hypergraphs[END_REF] to generalise the 1-2-3 Conjecture to hypergraphs, resulting in two variants defined over a similar terminology. For a hypergraph H and a labelling of the hyperedges of H, one can, again, compute c (v) for every vertex v, which is the sum of labels assigned by to the hyperedges containing v. The two works above introduce two possible ways to consider that is proper, a weak one and a strong one. In the weak one, is considered proper if, in every hyperedge, there are two vertices u and v with c (u) = c (v). In the strong one, is considered proper if, in every hyperedge, every two vertices u and v verify c (u) = c (v). In what follows, we consider the strongest definition only. We say that is proper if it verifies the strongest property. We say that H is nice if no two vertices are contained in the exact same set of hyperedges. Finally, assuming H is nice, we define χ Σ (H) as the smallest k such that proper k-labellings of H exist.

In brief, the authors of [START_REF] Bennett | Weak and Strong Versions of the 1-2-3 Conjecture for Uniform Hypergraphs[END_REF] focused on uniform hypergraphs only, and mainly gave conditions (for both the weak and strong variants of the problem) for a uniform hypergraph H to have a small constant value as χ Σ (H). They also studied the existence of uniform hypergraphs H having χ Σ (H) as large as possible, and proved that determining whether a uniform hypergraph admits proper 2-labellings is NP-complete.

For a given r ≥ 2, consider the following transformation from a graph to a hypergraph. Let G be a graph. We denote by L r (G) the hypergraph obtained from G by basically turning all edges into hyperedges containing all vertices at distance at most r. That is, G and L r (G) have the same vertex set, and, for every edge e of G, we have in H a hyperedge S e containing all vertices v of G with e ∈ E r G (v). This construction is illustrated in Figure 1. It can be observed that there is some equivalence between labelling a graph G and labelling the corresponding hypergraph L r (G). That is:

Theorem 2.1. Let r ≥ 2. If G is an r-nice graph, then χ r Σ (G) ≤ χ Σ (L r (G)). v 1 v 2 v 3 v 4 (a) P3 v 1 v 2 v 3 v 4 v 1 v 2 v 3 v 4 S v 2 v 3 S v 1 v 2 S v 3 v 4 (b) L 2 (P3)
Figure 1: The construction described in Subsection 2.1, performed with r = 2 and the path P3 of length 3.

The colours indicate the equivalence between the edges of P3 and the hyperedges of L 2 (P3).

Proof. Set H = L r (G). Note first that if H was not nice, then this would imply that G has two vertices u and v with E r G (u) = E r G (v), contradicting that G is r-nice. Thus, H must be nice. Now, consider a proper k-labelling of H, and let be the k-labelling of G obtained by setting (e) = (S e ) for every edge e ∈ E(G). As a result, we have c r (v) = c (v) for every vertex v ∈ V (G). Now, for every two vertices u and v of G that are at distance at most r apart, note that there must be an edge e ∈ E r G (u) ∩ E r G (v) (consider e.g. an edge e on a shortest path from u to v). Then {u, v} ⊂ S e , which implies that c (u) = c (v), and thus c r (u) = c r (v). We thus deduce that is r-proper, and the result follows.

Despite being a promising approach, we do not seem to deduce anything particular from, notably, the results on proper labellings of hypergraphs from [START_REF] Bennett | Weak and Strong Versions of the 1-2-3 Conjecture for Uniform Hypergraphs[END_REF]. The main reason for that, being that, given a graph G, the uniformity of L r (G) is far from being guaranteed in general (which is one of the key assumption made through the results in [START_REF] Bennett | Weak and Strong Versions of the 1-2-3 Conjecture for Uniform Hypergraphs[END_REF]). Also, it is important to note that the connection between the two notions of properness proved in Theorem 2.1 is a bit off in general, in the sense that proper labellings of hypergraphs are stronger that r-proper labellings of graphs. Namely, G might have two vertices u and v at distance more than r from each other having a common edge e at distance r. Then, a proper labelling of L r (G) guarantees that u and v get distinct colours (since they belong to the hyperedge S e ), while this is not a needed requirement for their r-colours in an r-proper labelling of G. Thus, while this hypergraph approach remains an interesting alternative formulation for our problem, it might be far from being a viable way to look at it in general.

Irregular labelling and irregularity strength

For every r ≥ 2, we can establish a connection between r-proper labellings and irregular labellings, thus between the parameters χ r Σ and s. More precisely, for every nice graph G, we can construct a graph S r (G) with χ r Σ (S r (G)) ≥ s(G), in the following way (see Figure 2 for an illustration). For every vertex v ∈ V (G), we add a clique vertex w v to S r (G). We add an edge between any two clique vertices in S r (G), so that they form a clique on |V (G)| vertices. Next, for every edge e ∈ E(G), we add, to S r (G), a new path P e = (s e , . . . , t e ) of length r -1, where its r vertices are new path vertices. Also, for every vertex v of G with incident edges e 1 , . . . , e d (where d = d G (v)), we add the edges w v s e 1 , . . . , w v s e d to S r (G). We finish off the construction, by adding a path Q = (x 1 , . . . , x r ) of length r -1, and joining x 1 and all w v 's. We also regard the vertices of Q as path vertices. We say that every vertex w v of S r (G) is associated to v, while the only edge incident to a vertex t e is the edge of S r (G) associated to e. We also call such an edge incident to t e a pending edge.

v 1 v 2 v 3 v 4 (a) S3 wv 1 wv 2 wv 3 wv 4 sv 1 v 4 tv 1 v 4 sv 2 v 4 tv 2 v 4 sv 3 v 4 tv 3 v 4 x 1 x 2 x 3 (b) H 3 (S3)
The unique edge incident to x r in Q is also seen as a pending edge. Later on, whenever dealing with this construction, we will stick to the terminology we have just used. We start by showing that S r (G) is r-nice as soon as G is nice.

Lemma 2.2. Let r ≥ 2. If G is a nice connected graph, then S r (G) is r-nice.
Proof. Let H = S r (G). Note that every vertex of H is essentially either a clique vertex (a vertex w v associated to a vertex v of G), or a path vertex (either a vertex x i part of Q, or a vertex part of a path P e associated to an edge e of G). We show that no two vertices of H have the exact same edge-ball of radius r.

• Assume w u and w v are two clique vertices of H, being associated to u and v in G.

Because G is nice, then, without loss of generality, we have that u is incident to an edge ux with x = v. Then, we have E r H (w u ) = E r H (w v ) due to the pending edge of P ux belonging to E r H (w u ) and not to E r H (w v ).

• Assume u and v are two path vertices of H from paths P and P (being possibly the same). If P = P , then E r H (u) = E r H (v) due to the pending edge of P belonging to E r H (u) and not to E r H (v) (and similarly for the pending edge of P , belonging to E r H (v) and not to E r H (u)). If P = P , then, assuming, without loss of generality, that u is closer than v to the clique vertices, it can be noted that E r H (u) contains an edge from another path P (which exists since G is nice, implying that there are at least three such hanging paths in H) that is not contained in E r H (v). Thus, here as well, E r H (u) = E r H (v).

• Assume w u is a clique vertex of H and v a path vertex part of a path P . By construction, there is another path P whose pending edge is at distance exactly r from w u . This is because of the presence of Q, and because the vertex u in G associated to w u has degree at least 1 (by the connectedness of G). Then E r H (w u ) = E r H (v) due to this pending edge being at distance strictly more than r from v in H.

Thus, any two vertices of H have distinct edge-balls of radius r, and H is r-nice.

The connectivity requirement for G in Lemma 2.2 is to guarantee the r-niceness of S r (G) in case G has an isolated vertex. It is worth mentioning that we could get rid of this requirement, by tweaking the construction of S r (G) a bit, by simply adding another path Q having the exact same properties as Q.

We can now establish the following connection between any nice graph G and S r (G):

Theorem 2.3. Let r ≥ 2. If G is a nice connected graph, then s(G) ≤ χ r Σ (S r (G)).
Proof. Set H = S r (G). By Lemma 2.2, we have that H is r-nice. Furthermore, observe that, for every clique vertex w v of H, the edge-ball B r H (w v ) of radius r includes all nonpending edges. In other words, for every two clique vertices w u and w v of H, the edge-balls B r H (w u ) and B r H (w v ) only differ because of pending edges. More precisely, for every edge of G incident to u and not incident to v, we have that the associated pending edge in H belongs to E r H (w u ) and not to E r H (w v ), and vice versa. This is because a pending edge of H belongs to E r H (w u ) (E r H (w v ), resp.) if and only if the associated edge in G is incident to u (v, resp.). Note also that all the edges of Q belong to E r H (w v ) for every clique vertex w v . Thus, by a labelling of H, so that the r-colours c r (w u ) and c r (w v ) differ, it must be that the sum of the labels assigned to the pending edges (not in Q) in E r H (w u ) is different from the sum of the labels assigned to the pending edges (not in Q) in E r (w v ). From all these arguments, we deduce that if is an r-proper k-labelling of H, then, by assigning label (t e ) to every edge e of G, we obtain an irregular k-labelling of G. This implies that s(G) ≤ χ r Σ (H).

Theorem 2.3 will be particularly useful in later Section 4, for establishing general lower bounds on the parameters χ r Σ . At this point, let us indeed recall that the irregularity strength s(G) of a connected graph G can be as large as |V (G)| -1, as proved by Nierhoff [START_REF] Nierhoff | A Tight Bound on the Irregularity Strength of Graphs[END_REF], which bound can be attained for some graphs, as shown for example by stars.

Proper edge-colouring and chromatic index

Recall that, for a given graph G, an edge-colouring is proper if no two adjacent edges, i.e., sharing a vertex, are assigned the same colour. The chromatic index of G, denoted by χ (G), is the smallest k such that proper k-edge-colourings of G exist. By a celebrated result of Vizing [START_REF] Vizing | On an estimate of the chromatic class of a p-graph[END_REF], it is known that χ (G) is always one of two possible values, namely ∆(G) or ∆(G) + 1. In the former case, we say that G is of class 1, while we say it is of class 2 in the latter case. For every fixed k ≥ 3, it is NP-complete to determine whether a given k-regular graph is of class 1 (see [START_REF] Leven | NP-Completeness of Finding the Chromatic Index of Regular Graphs[END_REF]). Through a particular graph construction, we can establish a general connection between the parameters χ r Σ and χ , for every r ≥ 2. More precisely, given a nice graph G, we can construct a graph H r (G) verifying χ r Σ (H r (G)) ≥ χ (G). The construction is as follows (see Figure 3 for an illustration). Let G be a graph, and let r ≥ 2 be any fixed integer. The graph H r (G) is obtained from G by basically "exploding" every vertex v to a clique on d G (v) vertices, and replacing the original edges with paths of length 2r -1. The formal details are as follows. For every vertex v in G with incident edges e 1 , . . . , e d (where d = d G (v)), we add d new vertices w v,e 1 , . . . , w v,e d to H r (G), between which we add all possible edges to form a clique on d vertices. We next consider every edge uv of G, and add a new path P uv of length 2r -1 to H r (G) joining w u,uv and w v,uv . For every v ∈ V (G), we call any vertex w v,e of H r (G) a clique vertex (associated to v), while, for every e ∈ E(G), we call P e an edge path (associated to e). For every edge path of H r (G), we call its inner vertices path vertices. Finally, in every edge path P uv of H r (G), we note that, by construction, there is exactly one edge that is at distance exactly r from both w u,uv and w v,uv ; we call this edge the middle edge of P uv (associated to uv). Throughout this paper, whenever dealing with this construction, we do so employing the terminology above.

Before proceeding, let us point out that H r (G) is r-nice whenever G is nice.

Lemma 2.4. Let r ≥ 2. If G is a nice graph, then H r (G) is r-nice.
Proof. Let H = H r (G). Recall that every vertex of H is either a clique vertex or a path vertex. Let us show that any two vertices of H at distance at most r apart, have distinct edge-balls of radius r.

• Assume w u,e and w v,f are two clique vertices of H. Note that we must have u = v for w u,e and w v,f to be at distance at most r from each other. Thus, assume u = v. Then, we have E r H (w u,e ) = E r H (w v,f ) due to the middle edge of P e belonging to E r H (w u,e ) and not to E r H (w v,f ) (and, analogously, the middle edge of P f belonging to E r H (w v,f ) and not to E r H (w u,e )).

• Assume w u,e is a clique vertex and x is a path vertex of H. So that w u,e and x are at distance at most r, note that x must belong to an edge path P f , where f is an edge incident to u in G (possibly f = e). We note that E r H (w u,e ) = E r H (x) due to an edge of P f being closer to the clique vertex of P f that is the farther from w u,e (which edge is at distance at most r from x but more than r from w u,e ).

• Assume x and y are two path vertices of H. So that x and y are at distance at most r, they must be in one of three possible configurations: denoting w u,e and w v,f the clique vertices that are the closest to x and y, respectively, then either 1) u = v (in which case e = f and x and y lie on P e ), or 2) u = v and e = f (in which case x and y lie on P e as well), or 3) u = v and e = f (in which case x lies on P e while y lies on P f ). In case 1), we have E r H (x) = E r H (y) due to edges incident to clique vertices associated to u belonging to E r H (x) and not to E r H (y), or due to edges incident to clique vertices associated to v belonging to E r H (y) and not to E r H (x) (note that we must fall in at least one of these two cases, as G is nice which implies that we cannot have d G (u) = d G (v) = 1). In case 2), we have E r H (x) = E r H (y), due to edges of P e belonging to only the one of E r H (x) and E r H (y) that is associated to the one of x and y that is the more distant from w u,e . In case 3), we have E r H (x) = E r H (y) due to edges of P e belonging to E r H (x) and not to E r H (y) (and, conversely, edges of P f belonging to E r H (y) and not to E r H (x)).

Thus, H is r-nice whenever G is nice.

For any r ≥ 2, the connection of interest between any nice graph G and H r (G) is then:

Theorem 2.5. Let r ≥ 2. If G is a nice graph, then χ (G) ≤ χ r Σ (H r (G)).
Proof. Let H = H r (G). By Lemma 2.4, we get that H is r-nice. Observe also that, for any two clique vertices w u,e and w u,f of H (associated to a same vertex u of G), the edge-balls B r H (w u,e ) and B r H (w u,f ) differ only by the middle edges of P e and P f (that is, the middle edge of P e lies in B r H (w u,e ) but not in B r H (w u,f ), and conversely the middle edge of P f lies in B r H (w u,f ) but not in B r H (w u,e )). This implies that for every vertex v ∈ V (G) with d ≥ 2 incident edges e 1 , . . . , e d , the middle edges of H associated to e 1 , . . . , e d must be assigned d distinct labels in any r-proper labelling of H. Thus, given an r-proper k-labelling of H, we obtain a proper k-edge-colouring of G by assigning colour x to every edge e, where x is the label assigned by to the middle edge of P e . This gives our conclusion.

Similarly as for the construction S r introduced earlier, this construction H r will be used in later Section 4 to illustrate that χ r Σ is, in general, not bounded above by an absolute constant. This construction will also be used in next Section 3 to establish the NP-completeness of the problem of determining χ r Σ (G) for a given r-nice graph G, using the fact that determining the chromatic index of a graph is itself an NP-hard problem.

The hardness of determining χ r

Σ

We here study the algorithmic complexity of determining χ r Σ (G) for an r-nice graph G, where r ≥ 2 is any fixed integer. That is, we consider the following decision problem: As a main result, we essentially prove that, for every r ≥ 2, the r-Proper k-Labelling problem is NP-hard. More precisely, we prove this for all pairs (r, k) where r = 2 and k ≥ 3, and where r ≥ 3 and k ≥ 6. Since the r-Proper k-Labelling problem is clearly in NP for every r and k, our results actually imply the NP-completeness of these problems. We mainly prove these results through the connection with proper edge-colouring, established in previous Subsection 2. [START_REF] Baudon | On decomposing regular graphs into locally irregular subgraphs[END_REF] is NP-hard, for every k ≥ 3 (see [START_REF] Leven | NP-Completeness of Finding the Chromatic Index of Regular Graphs[END_REF]). Our reduction strategy actually consists in modifying the construction H r (G) by a bit, so that χ (G) = k if and only if χ r Σ (H r (G)) = k. These modifications we introduce depend on the value of r (see Figure 4), which explains why our result is split into two parts. We start with the easier of the two proofs, that for r = 2.

r-Proper k-Labelling Input: An r-nice graph G. Question: Do we have χ r Σ (G) ≤ k? (a) r = 2 (b) r ≥ 3
Theorem 3.1. 2-Proper k-Labelling is NP-hard for every k ≥ 3.
Proof. Let k ≥ 3 be fixed. We prove the result by reduction from the Proper k-Edge-

Colouring problem. That is, from a k-regular graph G being an instance of Proper k-Edge-Colouring, we construct, in polynomial time, a graph H, such that χ (G) = ∆(G) = k if and only if χ 2 Σ (H) = k.
Note that we may assume that G is different from a complete graph, as the chromatic index of complete graphs is well known. Also, G cannot be an (odd-length) cycle since k ≥ 3.

To obtain H, we start from the graph H 2 (G) constructed from G as described in Subsection 2.3. We modify this graph by considering every clique vertex w v,e , and adding a new leaf vertex w v,e adjacent to w v,e (through the leaf edge w v,e w v,e ). The resulting H is clearly constructed in polynomial time. It remains to prove the desired equivalence.

Assume first that we have a 2-proper k-labelling of H. Let us consider the k-edgecolouring of G obtained by considering every edge uv, and assigning to uv, as a colour, the label assigned to the middle edge of H associated to uv. As described in the proof of Theorem 2.5, this results in a proper k-edge-colouring of G, and G is thus of class 1.

Conversely, assume that we have a proper k-edge-colouring φ of G. We construct a k-labelling of H, in the following way. We first consider every edge uv of G, and assign label φ(uv) to the middle edge of H associated to uv. Next, we label the leaf edges as follows. Since G is k-regular and is assumed to be different from a complete graph and an odd-length cycle, by Brooks' Theorem (see [START_REF] Brooks | On colouring the nodes of a network[END_REF]) there is a proper k-vertex-colouring ψ of G. Now, to every leaf edge w v,e w v,e of H, we assign, by , colour ψ(v) as a label. It remains to label all edges of H that are neither middle edges nor leaf edges (these edges are part of the cliques and of the edge paths); we assign label k to all these edges.

Let us now analyse the resulting 2-colours by for the vertices of H. Note that there are essentially three types of vertices to consider, namely 1) the clique vertices, 2) the path vertices, and 3) the leaf vertices. By carefully checking the edge-balls of radius 2, it can be noted that their 2-colours are as follows:

• If w v,e is a clique vertex, then c 2 (w v,e ) = k k(k-1) 2 + k + φ(e) + kψ(v).
• If x is a path vertex from an edge path P uv , then note that x is adjacent to exactly one of w u,uv and w v,uv . In the former case, we have c 2 (x) = k(k + 1) + φ(uv) + ψ(u), while, in the latter case, we have

c 2 (x) = k(k + 1) + φ(uv) + ψ(v). • If w v,e is a leaf vertex, then c 2 (w v,e ) = k 2 + ψ(v).
From this, it can be checked that if w v,e is a clique vertex of H and that x is any path vertex or leaf vertex at distance at most 2 from w v,e , then c 2 (w v,e ) > c 2 (x). Similarly, if x is any path vertex and u is any leaf vertex at distance at most 2 from x, then c 2 (x) > c 2 (u ). Thus, to establish the 2-properness of , it remains to compare 2-colours of vertices of the same type that are at distance at most 2. Actually, note that this does not have to be checked for pairs of leaf vertices of H, since no two such vertices are at distance at most 2. Now, for any two clique vertices w v,e and w v ,e to be at distance at most 2, note that we must have v = v , in which case c 2 (w v,e ) = c 2 (w v ,e ) because φ(e) = φ(e ). Lastly, for any two path vertices x and x of H to be at distance at most 2, note that x and x must belong to a same edge path P uv (thus being the two ends of the middle edge associated to uv); in that case, we have

c 2 (x) = c 2 (x ) because ψ(u) = ψ(v).
Thus, is a 2-proper k-labelling of H, and the equivalence between G and H holds.

We now turn our attention to proving a similar result when r ≥ 3.

Theorem 3.2. Let r ≥ 3 be fixed. r-Proper k-Labelling is NP-hard for every k ≥ 6.

Proof. Let r ≥ 3 and k ≥ 6 be fixed. We again prove the result by reduction from the Proper k-Edge-Colouring problem. From a k-regular graph G, we construct, in polynomial time, a graph

H such that χ (G) = ∆(G) = k if and only if χ r Σ (H) = k.
Again, we can assume that G is neither a complete graph nor an odd-length cycle.

The construction of H is as follows. We start from H being H r (G). We now consider every vertex v of G (with incident edges e 1 , . . . , e k ), and add to H a new dominating vertex x v joined to the unique neighbour of w v,e 1 on P e 1 , to the unique neighbour of w v,e 2 on P e 2 , and so on, to the unique neighbour of w v,e k on P e k , so that x v gets degree k. We also join x v to a new leaf vertex x v joined to x v only (resulting in the leaf edge x v x v ). Clearly, the construction of H is achieved in polynomial time.

Just as in the proof of Theorem 3.1, we can deduce a proper k-edge-colouring of G from an r-proper k-labelling of H, by similar arguments. In what follows, we thus focus on proving the other direction of the equivalence. So, let φ be a proper k-edge-colouring of G.

We consider the k-labelling of H obtained as follows. We first consider every edge e of G, and assign, by , label φ(e) to the middle edge of H associated to e. We then consider a proper k-vertex-colouring ψ of G, and, for every vertex v of G, assign label ψ(v) to the leaf edge x v x v of H. Finally, we assign label k to all other edges of H, i.e., all edges that are neither middle edges nor leaf edges. Our goal now, is to prove that is r-proper.

To simplify the exposition of the upcoming arguments, we classify the edges of H into three types. Leaf edges are yellow edges. Middle edges are green edges. All other edges are red edges. For every vertex v ∈ V (H), we define Y (v), G(v), R(v) as the sets of yellow, green, and red edges, respectively, at distance at most r from v. For convenience, we also set

y(v) = |Y (v)|, g(v) = |G(v)| and r(v) = |R(v)|. So, for every vertex v ∈ V (G), we have c r (v) = e∈Y (v) (e) + e∈G(v) (e) + e∈R(v) (e). Note that e∈R(v) (e) = kr(v).
By carefully checking the edge-balls of radius r of the vertices of H, note that:

Claim 1. The vertices of H verify:

• if x v is a leaf vertex, then y(x v ) = 1 and g(x v ) = 0. Furthermore, Y (x v ) = {x v x v }; • if x v is a dominating vertex, then y(x v ) = 1 and g(x v ) = k. Furthermore, Y (x v ) = {x v x v } and G(x v ) = {e 1 , . . . , e k }
, where e 1 , . . . , e k are the middle edges of H associated to the k edges incident to v in G;

• if u is any other vertex, then y(u) = 1 and g(u) = 1. Furthermore, Y (u) = {x v x v } and G(u) = {e }, where w v,e is the clique vertex of H that is the closest to u (possibly u = w v,e
) and e is the unique middle edge at distance at most r from u.

Exploiting Claim 1, the r-properness of is essentially guaranteed by the fact that pairs of vertices at distance at most r in H have their r-colours being different, either due to 1) a distinct number of red edges in their edge-balls of radius r (guaranteeing that one of the two r-colours is "much bigger" than the other), or 2) distinct sets of green and/or yellow edges (guaranteeing distinct r-colours modulo k). In particular, pairs of vertices at distance at most r from each other, having the same number of red edges in their edgeballs of radius r, share the similar unique green edge and a distinct unique yellow edge at distance at most r, or vice versa. More precisely: Claim 2. Let u and v be two vertices of H being at distance at most r. Then: • if u and v are two path vertices on different edge paths, then

• if u and v are two clique vertices, then G(u) = G(v) and Y (u) = Y (v); • if u is a clique vertex and v is a path vertex having u as the closest clique vertex, then G(u) = G(v) and Y (u) = Y (v); • if u is a clique vertex
G(u) = G(v) and Y (u) = Y (v).
An important point, is thus computing precisely the number of red edges at distance at most r from any vertex of H. We do this by making the distinction between several different types of vertices. Observe that any path vertex of H has its closest clique vertex being at distance at most r -1, and recall that r ≥ 3. Claim 3. Let v be a vertex of H; then:

• if v is a clique vertex, then r(v) = C 0 = k(k-1) 2 + kr; • if v is a dominating vertex v, then r(v) = C 0 ; • if v is a leaf vertex, then r(v) = C 0 -k(k-1) 2 = kr (if r = 3) or r(v) = C 0 (otherwise); • if v is a path vertex neighbouring a clique vertex, then r(v) = C 1 = C 0 + 1; • if v is a path vertex such that the closest clique vertex is at distance i ∈ {2, . . . , r -2}, then r(v) = C i = C 0 -(i -1)(k -1) + i; • if v is a path vertex such that the closest clique vertex is at distance r -1, then r(v) = C r-1 = 2r + 2k -2.
In particular, observe that:

Claim 4. C 1 > C 0 > C 2 > C 3 > • • • > C r-2 > C r-1 .
Proof of the claim. Obviously,

C 1 > C 0 . Since C 2 = C 0 -k + 3 ≤ C 0 -1 (because k > 3), we have C 0 > C 2 . For every i ∈ {2, . . . , r -3}, we have C i+1 = C i -k + 2, which is strictly smaller than C i since k > 2. Finally, note that C r-2 -C r-1 = k(k -1) 2 + kr -(r -3)(k -1) + r -2 -(2r + 2k -2) = k(k -1) 2 + k -3,
which is strictly positive since k > 3.

We are now ready to prove that is r-proper. Let u and v be two vertices of H being at distance at most r from each other.

• If u and v are clique vertices, then they are adjacent, in which case

R(u) = R(v), Y (u) = Y (v), and
G(u) = G(v) with g(u) = g(v) = 1; thus, c r (u) = c r (v).
• If u and v are path vertices lying on a same edge path, then let us denote by i the distance between u and its closest clique vertex a, and by j the distance between v and its closest clique vertex b.

-If a = b, then i = j. Without loss of generality, assume that i < j. Then

G(u) = G(v), Y (u) = Y (v), and r(u) > r(v); thus c r (u) > c r (v).
-If a = b, then u and v lie on different sides of the middle edge of the edge path they belong to. Necessarily,

G(u) = G(v), while Y (u) = Y (v) (but y(u) = y(v) = 1). If i = j, then r(u) = r(v)
, in which case c r (u) and c r (v) are different since y(u) = y(v) = 1. Now, if, say, i < j, then r(u) > r(v). Note that the absolute value of the difference between the label assigned to the edge in Y (u) and the label assigned to the edge in Y (v) is at most k -1. This implies that c r (u) > c r (v).

• If u and v are path vertices lying on different edge paths, then, without loss of generality, u is at distance i from its closest clique vertex w x,e and v is at distance j from its closest clique vertex w y,e . Because u and v are at distance at most r from each other, actually x = y. Now:

-If i = j, then Y (u) = Y (v), r(u) = r(v) and G(u) = G(v) (but g(u) = g(v) = 1). Thus c r (u) = c r (v).
-

If i = j, then assume i < j. Then Y (u) = Y (v) and r(u) > r(v); because G(u) = G(v) and g(u) = g(v) = 1, we have c r (u) > c r (v).
• If u is a clique vertex and v is a path vertex, then, as pointed out in Claim 2, there are three possible configurations:

v has u as the closest clique vertex. In this case, we have

G(u) = G(v) and Y (u) = Y (v)
. Furthermore, we have r(u) = r(v). Thus, c r (u) = c r (v).

v does not have u as the closest clique vertex, and v lies on the unique edge path incident to u. We here have

G(u) = G(v) and Y (u) = Y (v). Since y(u) = y(v) = 1
, we deduce that c r (u) ≡ c r (v) mod k, and thus c r (u) = c r (v).

v does not have u as the closest clique vertex, and v does not lie on the unique edge path incident to u. Here, note that we have

G(u) = G(v) and Y (u) = Y (v)
since u and v are at distance at most r from each other. Again, because g(u) = g(v) = 1, this implies that c r (u) ≡ c r (v) mod k, and thus that c r (u) = c r (v).

• If u is a clique vertex and v is a dominating vertex, then u and v are at distance 2, in which case

R(u) = R(v), Y (u) = Y (v), and
g(u) = 1 < k = g(v) (particularly, G(u) ⊂ G(v)); thus, c r (v) > c r (u).
• If u is a clique vertex and v is a leaf vertex, then u and v are at distance 3, in which case r(u

) ≥ r(v ), G(u) = G(v ) = ∅, and
Y (u) = Y (v ); thus, c r (u) > c r (v ).
• If u is a leaf vertex and v is a dominating vertex, then u and v are neighbours, in which case R(u

) ⊆ R(v), Y (u ) = Y (v), and
G(u ) = ∅ = G(v); thus, c r (v) > c r (u ). • If u is a leaf vertex and v is a path vertex, then Y (u ) = Y (v) and G(u ) = ∅ = G(v).
Recall that g(v) = 1. If the middle edge of the path edge that contains v is not assigned label k, then note that c r (u ) = c r (v) because c r (u ) ≡ c r (v) mod k (because c r (u ) is congruent to the label assigned to the unique edge in Y (u ) modulo k). Thus, assume that this middle edge is assigned label k.

-

If r = 3, then c r (u ) = k(3k) + (uu ) = 3k 2 + (uu )
, where, recall, u is the only (dominating) neighbour of u , while c r (v) = k(C i + 1) + (uu ) for some i ∈ {1, 2} (i being the distance between v and its closest clique vertex). Note that we cannot have c r (u ) = c r (v) if i = 1 (this would require k(k-1)

2

= -2). For the case i = 2, it can be checked that c r (u ) = c r (v) only occurs if k = 5. Thus there cannot be equality, since we have assumed k ≥ 6.

-Otherwise, i.e., r ≥ 4, we have c r (u ) = kC 0 + (uu ) while c r (v) = k(C i + 1) + (uu ) for some i ∈ {1, . . . , r -1}. Since C 1 > C 0 , we have no conflict if i = 1.

Note further that

C 0 > C 2 + 1, because k > 4; since C 2 > C 3 > • • • > C r-1
, we also have no conflict for any i ∈ {2, . . . , r -1}.

• If u is a dominating vertex and v is a path vertex, then

Y (u) = Y (v), G(v) ⊂ G(u),
and either r(u) > r(v) or r(v) = r(u)+1 (case where v is adjacent to a clique vertex).

In the former case, we clearly have c r (u) > c r (v). We also reach the same conclusion in the latter case, because the set of labels assigned to the edges in G(u) is precisely {1, . . . , k}, g(v) = 1, and k > 4 (which implies that (k-1)(k-2) 2 > k).

Note that any two dominating vertices of H are at distance strictly more than r, and similarly for any two leaf vertices; thus, these cases do not have to be considered. Thus, every two vertices of H being at distance at most r apart do get distinct r-colours by , as desired, which concludes the proof.

Lower bounds on χ r

Σ

Our main goal in this section is to investigate how large can χ r Σ (G) be in general, for a given graph G. To this end, we exploit results introduced in previous sections as well as new approaches, to introduce graphs with various structures requiring more and more distinct labels in their r-proper labellings.

From the connections we have established with the irregularity strength and the chromatic index of graphs, recall Theorems 2.3 and 2.5, we can already state that, for any r ≥ 2, there is no constant bounding χ r Σ (G) above for every r-nice graph G.

Corollary 4.1. Let r ≥ 2. There is no absolute constant c r ≥ 1 such that χ r Σ (G) ≤ c r holds for every r-nice graph G.

Proof. Let c r ≥ 1 be a fixed constant. We simply observe that there exist r-nice graphs G with χ r Σ (G) > c r . Note indeed first that for any nice graph G with ∆(G) > c r , the graph H r (G) (defined in Subsection 2.3) is r-nice (by Lemma 2.4) and verifies χ r Σ (H r (G)) ≥ χ (G) ≥ ∆(G) > c r by Vizing's Theorem [START_REF] Vizing | On an estimate of the chromatic class of a p-graph[END_REF] and Theorem 2.5. A similar conclusion can be reached from any nice connected graph G with s(G) > c r , the modified graph S r (G) (defined in Subsection 2.2, which is r-nice by Lemma 2.2), and Theorem 2.3. Particularly, any nice connected graph G with more than c r degree-1 vertices verifies s(G) > c r .

Since, for any r ≥ 2, there is no absolute constant bounding χ r Σ (G) above for every r-nice graph G, a legitimate question is about the best way to express bounds on this parameter in general. From the two constructions used to prove Corollary 4.1, two parameters seem particularly appropriate, namely the graph's maximum degree ∆(G) (which is commonly used to bound the chromatic index) and the graph's order |V (G)| (which has been used to express bounds on the irregularity strength). Since r-proper labellings are more of a local concept (the maximum size of an edge-ball of radius r is more naturally defined as a function of the maximum degree), the former option seems the most appropriate, and this is the one we focus on. The reader should keep in mind, however, that any of the upcoming lower bounds could also be expressed as a function of the graph's order.

Exploiting further the relationship in Theorem 2.5, we can already establish that, for every r ≥ 2 and every ∆ ≥ 2, there exist graphs H with ∆(H) = ∆ and χ r Σ (H) ≥ ∆ + 1. To see this is true, consider any nice class-2 graph G with maximum degree ∆ (such graphs exist: for ∆ ≥ 3 because Proper k-Edge-Colouring is NP-complete for k = ∆, for ∆ = 2 because odd-length cycles have chromatic index 3 = ∆ + 1) and consider H = H r (G); the result then follows from Theorem 2.5. Observation 4.2. For every r ≥ 2 and ∆ ≥ 2, there exist graphs G with ∆(G) = ∆ and χ r Σ (G) ≥ ∆ + 1.

It actually turns out that there exist graphs G for which χ r Σ (G) is far beyond ∆(G) + 1 in terms of magnitude. Before proving that fact formally, which requires using totally different arguments, let us discuss a bit further the approach above, from which we can deduce interesting arguments regarding an upper bound to be established in later Section 5. Before proceeding, let us first prove a simple result as a warm up. Observation 4.3. Let r ≥ 2, and G be a graph with a path P = (v 1 , . . . , v 4r+2 ) where d(v i ) = 2 for every i ∈ {2, . . . , 4r + 1}. If G is r-nice, then χ r Σ (G) > 2.

Proof. Assume the claim is wrong, and let be an r-proper 2-labelling of G. For every i ∈ {1, . . . , 4r + 1}, let us denote by e i the edge v i v i+1 . So that c r (v r+1 ) = c r (v r+2 ), note that we must have (e 1 ) = (e 2r+1 ). Without loss of generality, we may suppose that (e 1 ) = 1 and (e 2r+1 ) = 2. Similarly, so that c r (v r+2 ) = c r (v r+3 ), note that we must have (e 2 ) = (e 2r+2 ). Now, so that c r (v r+1 ) = c r (v r+3 ), we must have (e 1 )+ (e 2 ) = (e 2r+1 )+ (e 2r+2 ).

Since (e 1 ) = 1 and (e 2r+1 ) = 2, we must have (e 2 ) = 1 and (e 2r+2 ) = 2. Similarly, so that c r (v r+2 ) = c r (v r+4 ), we must have (e 3 ) = 1 and (e 2r+3 ) = 2. Repeating these arguments (with successive pairs of vertices v r+i and v r+i+2 at distance 2), we deduce that e 1 , . . . , e 2r must be assigned label 1, while e 2r+1 , . . . , e 4r must be assigned label 2.

Due to the length of P , the edge e 4r+1 exists. So that c r (v 3r ) = c r (v 3r+2 ), we must have (e 2r ) + (e 2r+1 ) = (e 4r ) + (e 4r+1 ); thus (e 4r+1 ) = 2. Now the 2r + 1 consecutive edges e 2r+1 , . . . , e 4r+1 are assigned the same label, 2, by . From this, we deduce that c r (v 3r+1 ) = c r (v 3r+2 ), which contradicts the r-properness of .

To go just a bit beyond the lower bound in Observation 4.2, an idea could be, for an r ≥ 2 and a nice class-2 graph G with maximum degree ∆ ≥ 2, to investigate whether H = H r (G) admits an r-proper (∆+1)-labelling. This is indeed far from being guaranteed, as some of the middle edges in H are required to be assigned distinct labels, but nothing ensures that the other edges can be successfully labelled as desired. This is, in particular, far from being clear as some edge-balls of radius r in H intersect a lot.

We illustrate these thoughts with a simple case. The smallest nice class-2 graph is G = C 3 , since it verifies ∆(G) = ∆ = 2 while χ (G) = ∆ + 1 = 3. For every r ≥ 2, we note that H r (G) is nothing but C 6r , the cycle of length 6r. It turns out that χ r Σ (C 6r ) ≥ 4 = ∆(C 6r ) + 2 for every r ≥ 3. An interesting point, is that this fact stands as a generalisation of the fact that χ 1 Σ (C n ) = 3 for every n ≡ 0 mod 4, which is essentially because odd-length cycles have chromatic number 3 (see e.g. [START_REF] Bensmail | On Proper Labellings of Graphs with Minimum Label Sum[END_REF] for a more thorough argumentation). Proof. Let r ≥ 3 be fixed, and let C be C 6r , the cycle of length 6r. We denote by v 0 , . . . , v 6r-1 the consecutive vertices of C, where e i = v i v i+1 is an edge for every i ∈ {0, . . . , 6r -1} (where, throughout this proof, operations over the indexes are understood modulo 6r). Note that C is r-nice due to its length; let be a labelling of C. Because r ≥ 3, the following conditions (generalising those in the proof of Observation 4.3) must be met for to be r-proper:

1. for every i ∈ {0, . . . , 6r -1}, we must have (e i-r ) = (e i+r ) -this is to guarantee

c r (v i ) = c r (v i+1 ) since E r C (v i ) \ E r C (v i+1 ) = {e i-r } and E r C (v i+1 ) \ E r C (v i ) = {e i+r };
2. for every i ∈ {0, . . . , 6r -1}, we must have (e i-r ) + (e i-r+1 ) = (e i+r ) + (e i+r+1 ) -this is to guarantee c r

(v i ) = c r (v i+2 ) since E r C (v i ) \ E r C (v i+2 ) = {e i-r , e i-r+1 } and E r C (v i+2 ) \ E r C (v i ) = {e i+r , e i+r+1 };
3. for every i ∈ {0, . . . , 6r -1}, we must have (e i-r ) + (e i-r+1 ) + (e i-r+2 ) = (e i+r ) + (e i+r+1 )+ (e i+r+2 ) -this is to guarantee

c r (v i ) = c r (v i+3 ) since E r C (v i )\E r C (v i+3 ) = {e i-r , e i-r+1 , e i-r+2 } and E r C (v i+3 ) \ E r C (v i ) = {e i+r , e i+r+1 , e i+r+2 }.
Towards a contradiction, assume is an r-proper 3-labelling of C. Let us consider the three distinct triples T 1 = ( (e 0 ), (e 1 ), (e 2 )), T 2 = ( (e 2r ), (e 2r+1 ), (e 2r+2 )) and T 3 = ( (e 4r ), (e 4r+1 ), (e 4r+2 )). Due to the length of C, note that the T i 's must have their first, second and third elements to be different (to fulfil the first condition above), the sums of their first and second elements, and similarly of their second and third elements, to be different (to fulfil the second condition), and the sums of their three elements to be different (to fulfil the third condition). Without loss of generality, we may assume that (e 0 ) = 1, (e 2r ) = 2 and (e 4r ) = 3.

• Assume first that (e 1 ) = 2. Then, so that (e 0 ) + (e 1 ) = (e 2r ) + (e 2r+1 ), we must have (e 2r+1 ) = 3, and thus (e 4r+1 ) = 1. Now: The only remaining case is when (e 2 ) = 1. In that case, so that (e 4r+1 )+ (e 4r+2 ) = (e 1 ) + (e 2 ), we must have (e 4r+2 ) = 3 and, thus, (e 2r+2 ) = 2. Under those assumptions, note that, by the exact same reasoning, we deduce that we must have (e 3 ) = 1, (e 2r+3 ) = 2, and (e 4r+3 ) = 3. Repeating these arguments actually implies that the 2r successive edges e 0 , . . . , e 2r-1 must be assigned label 1, the 2r successive edges e 2r , . . . , e 4r-1 must be assigned label 2, and the 2r successive edges e 4r , . . . , e 6r-1 must be assigned label 3. But then we deduce that (e 6r-1 ) + (e 0 ) + (e 1 ) = 5 = (e 2r-1 ) + (e 2r ) + (e 2r+1 ), which is another contradiction.

-if (e 2 ) =
This contradicts the r-properness of , thus its existence, and concludes the proof.

It is worth mentioning that Theorem 4.4 is somewhat tight, because, for r = 2, the cycle C 12 actually admits 2-proper 3-labellings. To see this is true, just consider the 3-labelling assigning labels 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3 to the consecutive edges; it can be checked that this is indeed a 2-proper 3-labelling of C 12 . Through upcoming Lemma 4.6 (and Corollary 4.7), we will see that, actually, shorter cycles can be even more problematic.

As mentioned earlier, there exist, for any r ≥ 2, r-nice graphs G for which χ r Σ (G) is a function of ∆(G) of much higher order of magnitude than that of the lower bounds in Observation 4.2 and Theorem 4.4. To show this, we need some other concepts and notions.

For a given graph G, we denote by G ≡ the graph obtained from G as follows. We start from two disjoint copies G 1 and G 2 of G. Now, to form G ≡ , we add a perfect matching between the vertices of G 1 and those of G 2 , so that every edge added this way joins two copies of a given vertex in G. That is, if, for every v ∈ V (G), we denote by v 1 ∈ V (G 1 ) and v 2 ∈ V (G 2 ) its copies in G 1 and G 2 , then, to form G ≡ , we add every possible edge v 1 v 2 where v ∈ V (G). In other words, G ≡ is the Cartesian product G K 2 of G and K 2 .

To establish our result, we use this construction in conjunction with a class of graphs having peculiar distance properties. Namely, for a d ≥ 1, we say that a graph G is d-special if it has the following properties:

• diam(G) = d; • for every vertex v ∈ V (G), we have |E d+1 G (v) \ E d G (v)| = 1; • for any two distinct vertices u, v ∈ V (G), we have E d+1 G (u)\E d G (u) = E d+1 G (v)\E d G (v).
In other words, a d-special graph is a graph in which every two vertices are at distance at most d, all edge-balls of radius d contain all edges of the graph but one, and no two vertices miss the same edge in their edge-balls of radius d.

We note that d-special graphs do exist for every d ≥ 1; as an easy illustration, let us mention that every cycle C 2d+1 with odd length 2d + 1 is d-special. More graphs of this sort can also be constructed using the graph construction introduced earlier:

Lemma 4.5. Let k ≥ 1. If G is a k-special graph, then G ≡ is (k + 1)-special.
Proof. Due to the structure of G, it can be observed that, for every two (not necessarily distinct) vertices u, v ∈ V (G), we have dist

G ≡ (u 1 , v 2 ) = dist G (u, v) + 1. From this, we deduce that diam(G ≡ ) = diam(G)+1 = k +1. This also implies that if, for some v ∈ V (G), we have ab ∈ E x G (v), then we have a 2 b 2 ∈ E x+1 G ≡ (v 1 ). Also, because diam(G) = k, then every edge of the form u 1 u 2 of G ≡ belongs to E k+1 G ≡ (v 1
). From all these arguments, we deduce that

E k+2 G ≡ (v 1 ) \ E k+1 G ≡ (v 1 ) = {a 2 b 2 }, where ab is the unique edge of G that belongs to E k+1 G (v)\E k G (v).
In particular, no two distinct vertices of G ≡ have the same unique edge at distance k +2, as this would imply that G has two distinct vertices with the same unique edge at distance k + 1, contradicting that G is k-special. Thus, G ≡ is (k + 1)-special.

We can now provide a connection with r-proper labellings:

Lemma 4.6. Let r ≥ 2. If G is an r-nice r-special graph, then χ r Σ (G) ≥ |V (G)|.
Proof. By the definition of an r-special graph, for every vertex v ∈ V (G) we have E r+1 G (v) = E(G) \ {e v } for some edge e v ∈ E(G). Furthermore, we have e u = e v for every two distinct vertices u and v. Thus, so that c r (u) = c r (v) by a labelling , we must have (e u ) = (e v ). From this, we deduce that an r-proper labelling of G must assign unique labels to the edges in the set {e v : v ∈ V (G)}. Recall indeed that, by definition, G has diameter r, and thus every two vertices must get distinct r-colours by c r . The bound then follows.

As mentioned earlier, this result permits to go way beyond Theorem 4.4: every cycle C 2k+1 is k-special, and, as easily checked, is also k-nice. From Lemma 4.6, we deduce that χ k Σ (C 2k+1 ) ≥ 2k + 1, implying that a constant number of labels is not sufficient for all cycles and all radius values. As will be seen through later Theorem 5.3, these short cycles form actually a very pathological case. We now turn to proving our main result in this section:

Theorem 4.8. For every r ≥ 2, there exist graphs

G with ∆(G) = r + 1 and χ r Σ (G) ≥ 3 • 2 ∆(G)-2 .
Proof. Consider the sequence of graphs G 2 , G 3 , G 4 , . . . where G 2 is the graph C ≡ 3 (C 3 being the cycle of length 3), and, from this point onwards, G i = G ≡ i-1 for every successive i = 3, 4, . . . . We note that every G i is i-nice because, for every two vertices u, v ∈ V (G i ),

we have E i+1 G i (u) = E(G) \ {e u } and E i+1 G i (v) = E(G) \ {e v }
where e u and e v are two distinct edges. Since C 3 is clearly 1-special, then, by Lemma 4.5, we get that every G i is i-special, and, thus, from Lemma 4.6 we have

χ i Σ (G i ) ≥ |V (G i )| for every i ∈ {2, 3, . . . , }. If we define G 1 as C 3 , then we have |V (G 1 )| = 3 and |V (G i )| = 2|V (G i-1 )
| for every successive i = 2, 3, . . . . This defines a geometric sequence with initial value 3 and common ratio 2, from which we deduce that |V (G i )| = 3 • 2 i-1 for every i ∈ {1, 2, 3, . . . }. From Lemma 4.6, we thus deduce that χ i Σ (G i ) ≥ 3 • 2 i-1 for every i. To get our exact conclusion, it suffices to note, now, that, for any graph G, we have ∆(G ≡ ) = ∆(G) + 1. Thus, in our situation above, ∆(G i ) = i + 1 for every i, and

χ i Σ (G i ) ≥ 3 • 2 ∆(G i )-2 .

Upper bounds on χ r

Σ

Our goal in this section is to exhibit upper bounds on χ r Σ (G) for any given r-nice graph G (possibly having particular properties), where r ≥ 2. Let us first mention that, although we benefit a lot from existing bounds and approaches in the literature for the case r = 1 (for instance, from [START_REF] Kalkowski | Vertex-coloring edge-weightings: towards the 1-2-3 Conjecture[END_REF][START_REF] Karoński | Edge weights and vertex colours[END_REF]), it turns out that, unfortunately, most of them do not seem to generalise to larger radius, or, at least, not in an obvious way. The main source of trouble stems from the property that, in r-proper labellings, the r-colours are fetched from farther away, which spoils the mechanisms behind most techniques for the radius-1 case.

Let us start by trying to establish any upper bound, regardless of whether it is good or not. In the radius-1 approach, the most naive approach is to proceed by induction, by removing one vertex v from a given nice graph G, labelling the remaining graph G -v in a proper way, and extending this labelling to the edges incident to v. One technicality with this approach, is that G -v might be not nice anymore. However, this point can easily be bypassed, as, in the radius-1 case, there is only one connected obstruction, which is K 2 . Thus, if G -v is not nice, then there is a peculiar structure around v in G, and additional arguments can be employed to also label the edges forming that structure.

These thoughts lead to emphasising a negative point with r-proper labellings, which is that the set of (connected) obstructions is far from being clear for any given r ≥ 2, which makes inductive approaches even more uncertain. Mainly for this reason, we turn to a more algebraic approach, first developed in [START_REF] Bartnicki | Weight choosability of graphs[END_REF] to deal with the so-called List 1-2-3 Conjecture, which is a generalisation of the 1-2-3 Conjecture where edges are labelled with labels from dedicated lists of given size. The formal details are as follows. Let G be a nice graph. A k-list assignment L : E(G) → R k to the edges of G, assigns to every edge e ∈ E(G) a list L(e) of k labels. An L-labelling of G is a labelling where (e) ∈ L(e) for every edge e of G. As in the original problem, is proper if c (u) = c (v) for every two adjacent vertices u and v of G. Now, the parameter ch Σ (G) is the smallest k ≥ 1 such that proper L-labellings of G exist for every k-list assignment L to the edges of G. The List 1-2-3 Conjecture asserts that ch Σ (G) ≤ 3 should hold for every nice graph G. We refer the interested reader to [START_REF] Seamone | The 1-2-3 Conjecture and related problems: a survey[END_REF] for more details on the topic.

Note that these list concerns also adapt naturally for any larger radius r ≥ 2, from which we can define a dedicated parameter ch r Σ (G). In what follows, we will provide a general upper bound on the parameters ch r Σ , thus on the parameters χ r Σ , via arguments inspired from existing ones used to deal with the List 1-2-3 Conjecture. These arguments rely mainly on a non-constructive approach, which consists in describing the constraints in an r-proper labelling under the form of a polynomial, expanding the polynomial, and studying its monomials to make use of powerful tools such as Alon's Combinatorial Nullstellensatz [START_REF] Alon | Combinatorial Nullstellensatz[END_REF]:

Combinatorial Nullstellensatz. Let F be an arbitrary field, and let f = f (x 1 , . . . , x n ) be a polynomial in F[x 1 , . . . , x n ]. Suppose the total degree of f is n i=1 t i , where each t i is a non-negative integer, and suppose the coefficient of n i=1 x t i i is non-zero. If S 1 , . . . , S n are subsets of F with |S i | > t i , then there are s 1 ∈ S 1 , . . . , s n ∈ S n so that f (s 1 , . . . , s n ) = 0.

More precisely, we prove the following:

Theorem 5.1. Let r ≥ 2. If G is an r-nice graph with ∆(G) ≥ 3, then χ r Σ (G) ≤ ch r Σ (G) ≤ 4∆(G) 2r-1 .
Proof. Set k = 4∆(G) 2r-1 , and let L be any k-list assignment to the edges of G. To prove the claim, we prove that there exists an r-proper L-labelling of G. We use the Combinatorial Nullstellensatz to that aim.

Let us denote by v 1 , . . . , v n the vertices of G, by e 1 , . . . , e m its edges, and, for every i ∈ {1, . . . , m}, let X i be a variable associated to the edge e i . For every vertex v of G, we denote by C r (v) the sum of the variables associated to the edges at distance at most r from v; that is, C r (v) = e i ∈E r G (v) X i . Now consider the polynomial P G over the variables X 1 , . . . , X m defined as

P G (X 1 , . . . , X m ) = v i <v j ∈V (G) : dist(v i ,v j )≤r (C r (v i ) -C r (v j )) .
Note that an r-proper L-labelling of G exists if and only if there are l 1 ∈ L(e 1 ), . . . , l m ∈ L(e m ) such that P G (l 1 , . . . , l m ) = 0. Because G is r-nice, recall that we do not have

E r G (v i ) = E r G (v j )
for two vertices v i and v j at distance at most r in G; thus, P G does not vanish trivially, because of a factor being 0.

Let us focus on the expansion of P G . Because R[X 1 , . . . , X m ] is an integral domain, there must be a monomial M = cX t 1 1 . . . X tm m with non-zero coefficient c = 0. Note that all monomials in the expansion are actually of the same degree (being the number of factors in P G , i.e., the number of pairs of vertices of G at distance at most r), thus of maximum degree. All conditions are thus met to apply the Combinatorial Nullstellensatz onto M .

To get our bound, we focus on any variable X i in M , and want to prove an upper bound on its exponent t i . Note that this quantity t i is bounded by the number of pairs of vertices {u, v} at distance at most r from each other in G, such that X i contributes to at least one of C r (u) and C r (v).

• Set e i = xy. In the worst-case scenario, the vertices at distance at most r from e i induce, essentially, a perfect (∆(G) -1)-ary tree with height r -1 rooted at x, and a disjoint perfect (∆(G) -1)-ary tree with height r -1 rooted at y. Since a perfect d-ary tree with height h has d h+1 -1 d-1 vertices, we deduce that there are at most

A = 2 • (∆(G) -1) r -1 ∆(G) -2 ≤ 2∆(G) r-1
vertices of G at distance at most r from e i . Recall that ∆(G) ≥ 3.

• Let v be any vertex of G. In the worst-case scenario, the vertices at distance at most r from v induce a tree where all leaves are at distance r from v, while all nonleaf vertices have degree ∆(G). This is exactly a tree obtained by joining the roots of a complete (∆ -1)-ary tree with height r and of a complete (∆ -1)-ary tree with height r -1. Thus, there are at most

B = (∆(G) -1) r+1 -1 ∆(G) -2 + (∆(G) -1) r -1 ∆(G) -2 ≤ ∆(G) r + ∆(G) r-1 < 2∆(G) r
vertices at distance at most r from v in G.

We thus deduce that t i ≤ AB < 4∆(G) 2r-1

. Since this applies to all t i 's, the Combinatorial Nullstellensatz, applied to M , guarantees an r-proper L-labelling of G exists.

Note that the bound in Theorem 5.1 can be improved, by noting that, in the computation of the maximum value as t i , we do not have to take into account factors C r (v i )-C r (v j ) of P G such that X i contributes to both C r (v i ) and C r (v j ). This way, we can decrease the bound by at least a function linear in r. We have not taken this fact into account in our computation though, as this would still result in an upper bound of order O(∆(G) 2r-1 ).

The magnitude of the bound in Theorem 5.1 is exponential in r, which is not so off, as we have shown that there exist r-nice graphs G for which χ r Σ (G) is actually exponential in r, recall Theorem 4.8. Note also that a slight technicality in the computations in the proof, requires ∆(G) ≥ 3. Although an upper bound on χ r Σ (G) could also be obtained this way when ∆(G) = 2 by changing the computations a bit, since this case corresponds to very restricted graphs, namely paths and cycles, we here provide more accurate bounds.

Recall that, in these cases as well (at least that of cycles), there is no absolute constant bounding χ r Σ above for every r ≥ 2, recall Corollary 4.7. We show that, omitting the peculiar case of cycles that are barely r-nice, every r-nice graph G with ∆(G) = 2 has χ r Σ (G) being small, i.e., bounded by an absolute constant. This highlights an interesting phenomenon behind our problem, which is that there exist graphs G for which χ 1 Σ (G), χ 2 Σ (G), . . . do not fluctuate much. In other words, the number of needed labels in an r-nice labelling of a given graph G, does no have to grow with r.

Theorem 5.2. Let r ≥ 2. If P is an r-nice path, then χ r Σ (P ) ≤ 4.

Proof. We set n = |V (P )|, and denote by v 1 , . . . , v n the consecutive vertices of P , where e i = v i v i+1 is an edge for every i ∈ {1, . . . , n -1}. We assume that P comes with an implicit orientation, where, say, v 1 is the first vertex while v n is the last vertex, thereby defining an ordering over the vertices (and edges) of P . The fact that P is r-nice implies that n > 2r: note indeed that, whenever n ≤ 2r, any two adjacent middle vertices of P have the same edge-ball of radius r.

We may actually assume that n > 4r + 1. Indeed, if 2r < n < 4r + 2, then an r-proper 4-labelling of P is obtained when assigning label 4 to its first (n -2)/2 edges, label 1 to the next edge, and label 2 to the last (n -2)/2 edges. As going to be explained in more details below, this does result in an r-proper labelling of P , essentially because it partitions the vertices into at most three blocks of consecutive vertices, such that, within a same block or along two consecutive ones, the r-colours cannot be in conflict, either because of different parities or different values.

To prove the result, we essentially show that, depending on the length of P , we can apply one of several periodic labelling schemes to the consecutive edges of P (from first to last), resulting in a labelling that is r-proper. To guarantee this property, the resulting will guarantee certain r-colour values and parities for blocks of consecutive vertices of P .

Let us illustrate this through a first case. Let be a labelling of P obtained by applying the consecutive labels 1, . . . , 1, 3, . . . , 3, 2, 1, . . . , 1, 3, . . . , 3, 2, 1, . . . , 1, 3, . . . , 3, 2, . . . to the consecutive edges (from first to last), where the dotted parts mean that labels 1 and 3 are assigned to exactly 2r consecutive edges of P (if sufficiently many unlabelled edges remain). As a result, the vertices of P can be classified into blocks of four different types, in the following general way (not taking account, for now, the actual length of P ):

• the first r vertices v 1 , . . . , v r verify c r (v 1 ) = r, c r (v 2 ) = r + 1, . . . , c r (v r ) = 2r -1,
and form a set of size r and of type S (starting block );

• the next 2r + 1 vertices v r+1 , . . . , v 3r+1 verify c r (v r+1 ) = 2r, c r (v r+2 ) = 2r + 2, . . . , c r (v 3r+1 ) = 6r, and form a set of size 2r + 1 and of type A (ascending block );

• the next 2r vertices v 3r+2 , . . . , v 5r+1 verify c r (v 3r+2 ) = 6r -1, c r (v 3r+3 ) = 6r -3, . . . , c r (v 5r+1 ) = 2r + 1, and form a set of size 2r and of type D (descending block );

• from here on, the consecutive vertices of P alternate between blocks of type A and D (having the same properties as in the last two items), where the last block is truncated at v n-r (this vertex being the last vertex of P having both r preceding edges and r succeeding edges), and might thus be of size less than 2r + 1 (if it is of type A) or less than 2r (otherwise, if it is of type D);

• the last r vertices v n-r+1 , . . . , v n verify c r (v n-r+1

) > c r (v n-r+2 ) > • • • > c r (v n )
, the exact values of these r-colours depending on how the labelling pattern ends, and form a set of size r and of type E (ending block ).

• the last r vertices v n-r+1 , . . . , v n verify c r (v n-r+1

) > c r (v n-r+2 ) > • • • > c r (v n ),
similarly as in the case of the previous labelling pattern, and form the type-E block of size r.

By the same arguments as previously, the resulting is r-proper if the length of P makes v n-r being either the first vertex of a type-A block, or after the first r vertices of a type-D block (if it is of size more than r). This is achieved whenever (n mod 4r + 1) ∈ {3r + 2, . . . , 4r, 0, 1}. In this case, we thus have χ r Σ (P ) ≤ 4. Recall that n > 4r + 1, thus that n ≥ 4r + 2 whenever this case applies.

To deal with the last cases as n, we consider a slightly different labelling pattern, which is essentially the same as in the previous case except that the second time we assign label 4 to a group of 2r edges, we instead assign this label to a group of r edges only. The main difference here, is that the first type-A block is of size r + 1 only, as its vertices have consecutive r-colours 4r, 4r + 2, . . . , 6r. Here, we thus end up with being r-proper whenever (n mod 4r + 1) ∈ {2r + 2, . . . , 3r + 2}, and we have χ r Σ (P ) ≤ 4. In this case as well, it is important to keep in mind that the arguments work out because n > 4r + 1, which implies we actually have n ≥ 6r + 3 whenever this case applies. Proof. Let n = |V (C)|, and let us denote by v 0 , . . . , v n-1 the consecutive vertices of C, where e i = v i v i+1 is an edge for every i ∈ {0, . . . , n -1} (where, throughout the proof, all operations over the indexes are understood modulo n). As in the proof of Theorem 5.2, we assume that C is given with an implicit natural orientation, from which the notions of preceding and succeeding vertices/edges can be defined. We may assume that n > 4r + 1, as, for smaller values of n, an r-proper 9-labelling of C is obtained by assigning label 3 to a group of x consecutive edges, label 1 to the edge succeeding the last edge of that group, and label 9 to the remaining group of y = n -x -1 consecutive edges, so that x and y are chosen to be at least r and most 2r (note that this is possible, since n > 2r + 1). The reasons why this does result in an r-proper labelling, are the same as the ones we provide below for the more general case where n > 4r + 1.

Assume thus that n > 4r + 1. We prove the claim for this case, by showing that C admits an r-proper 9-labelling which we construct in two steps. During a first step, we will label most of the edges of C, by applying a certain periodic labelling pattern to the successive edges of C so that a certain number of properties are fulfilled by the resulting r-colours. Then, during a second step, we will finish off the construction of by labelling the remaining edges of C (if any), with making sure that is eventually r-proper.

The periodic pattern we will apply during the first step, goes as follows. Let us assume we apply labels starting from e 0 , then e 1 , and so on along C. We start by assigning label 3 to 2r -1 edges. To the next edge, we then assign label 1. To the next 2r -1 edges, we then assign label 6. To the next edge, we then assign label 2. To the next 2r -1 edges, we then assign label 3. This pattern is then repeated by repeating the following:

• we assign label 1 or 2 to the next edge, so that the assigned label is different from the last label in {1, 2} previously assigned to a single edge;

• we assign label 3 or 6 to the next 2r -1 edges, so that the assigned label is different from the label in {3, 6} assigned to the previous group of 2r -1 consecutive edges.

Assume we have applied this pattern onto d successive edges e 0 , . . . , e d-1 of C. Note that this completely determines the r-colours of the vertices v r , v r+1 , . . . , v d-r by , since all of these vertices have both their r preceding edges and their r succeeding edges being labelled. Furthermore, by how the labels were assigned, note that the first 2r vertices in (v r , v r+1 , . . . , v d-r ) have an r-colour being congruent to 1 modulo 3, the next 2r vertices have an r-colour being congruent to 2 modulo 3, the next 2r vertices have an r-colour being congruent to 1 modulo 3, etc. Thus, just as in the proof of Theorem 5.2, the vertices in (v r , v r+1 , . . . , v d-r ) form blocks of 2r consecutive vertices, every two successive of these blocks containing vertices with different r-colours (1 or 2) modulo 3, and such that, within a given block, the r-colours are strictly decreasing or increasing due to how the labels 3 and 6 were assigned alternatively. Thus, applying this labelling pattern onto consecutive edges of C, results in a (possibly) partial 9-labelling that is r-proper.

To explain how to label the remaining edges of C (if any), let us start by actually applying the labelling pattern above as much as possible. That is, we start from e 0 , apply label 3 to the first 2r -1 edges, and then, as long as C has sufficiently many unlabelled edges remaining, we apply label 1 or 2 to the next edge followed by assigning label 3 or 6 to the next 2r -1 next edges, sticking to the rules above. Note that this requires the length of C to be at least 4r -1, which is a condition that is fulfilled by how the proof is split.

We are thus left with less than 2r edges being unlabelled, which we label as follows. Regardless of how many edges are left, let us tweak the current (possibly partial) labelling by a bit, by just changing the label (either 3 or 6) assigned to the last block of 2r -1 consecutive edges, to 9. Note that this cannot create conflicts between the r-colours by the arguments above. In case there are no remaining unlabelled edges, then we can just consider the conclusion below. Otherwise, let us now denote by f 1 , . . . , f p the consecutive unlabelled edges of C, where 1 ≤ p ≤ 2r -1. Free to relabel the vertices, we might assume that f 1 is adjacent to an edge already labelled 3 while f p is adjacent to an edge already labelled 9. We assign label 6 to these p ≤ 2r -1 edges. As a result, we note that all vertices that were not among the blocks of vertices with r-colour congruent to 1 or 2 modulo 3, have a resulting r-colour being congruent to 0 modulo 3 (thus not in conflict with all other vertices). Now, we note that these consecutive vertices having r-colour congruent to 0 modulo 3, due to how the labels were assigned, have their r-colours forming a strictly increasing sequence (as following the edges f 1 , . . . , f p ). Thus, is r-proper, as required.

Conclusion

In this work, we have introduced a new generalisation of the 1-2-3 Conjecture where not only vertices within a certain distance r must get distinct sums of labels, but also these sums of labels are fetched within the same distance r. While our results show some comparable behaviours between the original problem (where r = 1) and the more general one (where r ≥ 2), they also show that there are notable differences between them. For instance, while all these problems tend to share the same general level of complexity (recall our results from Section 3), we have shown that, contrarily to the original case r = 1, in the more general case r ≥ 2 there is no absolute constant bounding χ r Σ (G) above for every r-nice graph G. Through our results in Sections 4 and 5, we have actually established that the maximum value of χ r Σ (G) for an r-nice graph G, is a function exponential in r. Lastly, our results also show more specific properties of our general problem. For instance, Theorems 5.2 and 5.3 show that, for a given graph G, increasing r does not have to increase χ r Σ (G) as well. The connections we have established, in Section 2, between our problem and other ones of graph theory, are another interesting meaningful aspect.

The problem introduced in this work being quite general, and our results being only partial, there are many interesting lines of research which could be subject to further work on the topic. Among such perspectives, let us mention the following ones:

• Towards understanding the parameters χ r Σ better, it would be interesting to try to strengthen our bounds in Theorems 4.8 and 5.1, i.e., to come up with graphs G with bigger values of χ r Σ (G) or with better general bounds on χ r Σ .

• The previous concern could be investigated for general graphs, and for restricted classes of graphs as well. The case of trees could be an appealing one. Note, in particular, that our Theorem 4.8 does not hold for trees. However, our approach (with proper edge-colouring) in the proof of Corollary 4.1 applies for trees, from which we deduce that, for every r ≥ 2, there exist trees T with χ r Σ (T ) ≥ ∆(T ). Trees T with χ r Σ (T ) ≥ ∆(T ) + 1 also exist: as an example, consider a bistar in which the two center vertices have degree ∆(T ), and subdivide all leaves to turn them into pending paths of length r. Our arguments for proving the upper bound in Theorem 5.1, however, does not seem to improve under the assumption that G is a tree. Thus, in this case, the gap between the lower and upper bounds is even bigger.

• Regarding the connections with other graph problems established in Section 2, we were not able to establish a similar connection between r-proper labellings and rproper labellings, for r < r . For instance, for any r ≥ 1, we wonder whether there is a special graph transformation turning any given r-nice graph G into an (r + 1)nice graph G such that χ r+1 Σ (G ) is some function of χ r Σ (G). Such a transformation, which could stand as a generalisation of the one in Subsection 2.2, would definitely lead to a better understanding over the different versions of the problem (i.e., with different r's).

• Regarding the complexity results in Section 3, there are some values of r and k for which our proof scheme does not establish the NP-hardness of r-Proper k-Labelling. In particular, it is probable that our reduction scheme can be modified to provide a similar result for r ≥ 3 and k ∈ {3, 4, 5}. For the remaining cases, all those where r > 1 and k = 2, note that our approach cannot be used, as the Proper k-Edge-Colouring problem is not NP-hard for this value of k. Thus, in those cases, it is likely that a different reduction scheme is needed. Trying to adapt the reduction scheme from e.g. [START_REF] Dudek | On the complexity of vertex-coloring edge-weightings[END_REF], in which the NP-hardness of the 1-Proper 2-Labelling problem was proved, could be a promising approach.

Another interesting question in that line, is the status of r-Proper k-Labelling when restricted to particular classes of graphs. Recall, for instance, that for r = 1 and k = 2 the problem is NP-hard in general [START_REF] Dudek | On the complexity of vertex-coloring edge-weightings[END_REF] but polynomial-time solvable in bipartite graphs [START_REF] Thomassen | The 3-flow conjecture, factors modulo k, and the 1-2-3-conjecture[END_REF]. Note that our reduction scheme in Section 3 produces graphs that are never bipartite. Thus, an interesting question could be to investigate whether our complexity results also hold for bipartite graphs.

• Theorems 5.2 and 5.3 show an interesting property of the parameters χ 1 Σ , χ 2 Σ , . . . , which is that, in general, for a graph G increasing r might have no drastic impact on χ r Σ (G). It would be interesting to investigate the opposite direction, i.e., to study cases of graphs G for which χ 1 Σ (G), χ 2 Σ (G), . . . vary a lot. One possible approach, could be to investigate graphs G for which we have χ r Σ (G) = 1 for specific values of r. For an r ≥ 2, we could consequently define an r-irregular graph G as a graph in which, for every two vertices u and v at distance at most r, we have |E r G (u)| = |E r G (v)|. Note that, indeed, if G is r-irregular, then χ r Σ (G) = 1. Note also that the notion of 1-irregular graphs coincide exactly with that of locally irregular graphs, studied notably in [START_REF] Baudon | On decomposing regular graphs into locally irregular subgraphs[END_REF]. This notion of irregularity leads to many questions of interest. For instance, for any fixed r ≥ 2, are there easy constructions of r-irregular graphs? Can a given graph G be r-irregular for different values of r? For different non-consecutive values of r?

• Still about Theorems 5.2 and 5.3, one possible direction could be to try to tighten the upper bounds they provide. For paths, recall that there exist paths P for which χ r Σ (P ) > 2 (by Observation 4.3), and it might be that r-proper 3-labellings exist for all paths (which we have proved for paths with convenient length only, in the proof of Theorem 5.2). Regarding cycles, our main goal was mainly to show that the configurations described in Corollary 4.1 are very pathological, in the sense that a constant number of labels is sufficient for most cycles, regardless of r. As a consequence, there is much more room for improvement over our bound in Theorem 5.3. By Corollary 4.7, recall that long enough cycles require labels 1, 2, 3, 4; one could suspect that, perhaps, in general r-nice cycles admit r-proper 4-labellings.

Figure 2 :

 2 Figure 2: The construction described in Subsection 2.2, performed with r = 3 and the star S3 with three leaves. The colours indicate the equivalence between the edges of S3 and some edges of H 3 (S3).

Figure 3 :

 3 Figure 3: The construction described in Subsection 2.3, performed from r = 2 and the complete graph K4 on four vertices. The colours indicate the equivalence between the edges of K4 and some edges of H 2 (K4).

Figure 4 :

 4 Figure4: Local modifications made on the construction H r to prove Theorems 3.1 and 3.2. The picture on the left illustrates the case where r = 2 (and k = 4), while the picture on the right illustrates that where r ≥ 3 (particularly, r = 3 and k = 4 here). In the latter picture, colours show the different types (yellow, green and red) of edges considered throughout the proof of Theorem 3.2. Wiggly edges are middle edges.

  through Theorem 2.5. Recall indeed that the problem Proper k-Edge-Colouring Input: A k-regular graph G. Question: Is G of class 1, i.e., do we have χ (G) = ∆(G) = k?

  and v is a path vertex not having u as the closest clique vertex, then either G(u) = G(v) and Y (u) = Y (v) (case where v lies on the unique edge path incident to u), or G(u) = G(v) and Y (u) = Y (v) (otherwise); • if u and v are two path vertices on a same edge path sharing the same closest clique vertex, then G(u) = G(v) and Y (u) = Y (v); • if u and v are two path vertices on a same edge path for which the closest clique vertices are different, then G(u) = G(v) and Y (u) = Y (v);

Theorem 4 . 4 .

 44 For every r ≥ 3, we have χ r Σ (C 6r ) ≥ 4 = ∆(C 6r ) + 2.

••

  1, then, so that (e 4r+1 ) + (e 4r+2 ) = (e 1 ) + (e 2 ), we must have (e 4r+2 ) = 3 and, thus, (e 2r+2 ) = 2. But then (e 2r ) + (e 2r+1 ) + (e 2r+2 ) = 7 = (e 4r ) + (e 4r+1 ) + (e 4r+2 ), which is a contradiction; if (e 2 ) = 2, then, so that (e 1 ) + (e 2 ) = (e 2r+1 ) + (e 2r+2 ), we must have (e 2r+2 ) = 3 and, thus, (e 4r+2 ) = 1. But then (e 4r ) + (e 4r+1 ) + (e 4r+2 ) = 5 = (e 0 ) + (e 1 ) + (e 2 ), which is a contradiction; if (e 2 ) = 3, then, so that (e 1 ) + (e 2 ) = (e 2r+1 ) + (e 2r+2 ), we must have (e 2r+2 ) = 1 and, thus, (e 4r+2 ) = 2. But then (e 0 ) + (e 1 ) + (e 2 ) = 6 = (e 2r ) + (e 2r+1 ) + (e 2r+2 ), another contradiction. Now assume (e 1 ) = 3. So that (e 4r ) + (e 4r+1 ) = (e 0 ) + (e 1 ), we must have (e 4r+1 ) = 2 and thus (e 2r+1 ) = 1. Now: if (e 2 ) = 1, then, so that (e 1 ) + (e 2 ) = (e 2r+1 ) + (e 2r+2 ), we must have (e 2r+2 ) = 2 and, thus, (e 4r+2 ) = 3. But then (e 0 ) + (e 1 ) + (e 2 ) = 5 = (e 2r ) + (e 2r+1 ) + (e 2r+2 ), which is a contradiction; if (e 2 ) = 2, then, so that (e 4r+1 ) + (e 4r+2 ) = (e 1 ) + (e 2 ), we must have (e 4r+2 ) = 1 and, thus, (e 2r+2 ) = 3. But then (e 4r ) + (e 4r+1 ) + (e 4r+2 ) = 6 = (e 0 ) + (e 1 ) + (e 2 ), which is a contradiction; if (e 2 ) = 3, then, so that (e 2r+1 )+ (e 2r+2 ) = (e 4r+1 )+ (e 4r+2 ), we must have (e 2r+2 ) = 1 and, thus, (e 4r+2 ) = 2. But then (e 4r ) + (e 4r+1 ) + (e 4r+2 ) = 7 = (e 0 ) + (e 1 ) + (e 2 ), another contradiction. Assume last that (e 1 ) = 1. Then, so that (e 2r ) + (e 2r+1 ) = (e 4r ) + (e 4r+1 ), we must have (e 2r+1 ) = 2, and thus (e 4r+1 ) = 3. Now: if (e 2 ) = 2, then, so that (e 1 ) + (e 2 ) = (e 2r+1 ) + (e 2r+2 ), we must have (e 2r+2 ) = 3 and, thus, (e 4r+2 ) = 1. But then (e 2r ) + (e 2r+1 ) + (e 2r+2 ) = 7 = (e 4r ) + (e 4r+1 ) + (e 4r+2 ), which is a contradiction; if (e 2 ) = 3, then, so that (e 1 ) + (e 2 ) = (e 2r+1 ) + (e 2r+2 ), we must have (e 2r+2 ) = 1 and, thus, (e 4r+2 ) = 2. But then (e 0 ) + (e 1 ) + (e 2 ) = 5 = (e 2r ) + (e 2r+1 ) + (e 2r+2 ), another contradiction.

Corollary 4 . 7 .

 47 For every r ≥ 2, we have χ r Σ (C 2r+1 ) = 2r + 1.

Theorem 5 . 3 .

 53 Let r ≥ 2. If C is a cycle with length more than 2r + 1, then χ r Σ (C) ≤ 9.

Acknowledgement

Thanks are due to Louis Esperet for suggesting the problem investigated in this work. The authors were supported by ANR project HOSIGRA (ANR-17-CE40-0022).

Note that any two vertices from a same block have distinct r-colours by . Also, for the vertices of the type-S block, the only vertices at distance at most r from another block, belong to the first type-A block, and these vertices have larger r-colours by . Apart from this, the only vertices at distance at most r apart in P belonging to different blocks, either belong 1) to a type-A block and a neighbouring type-D block, or 2) to the type-E block and the first-to-last block (being of type A or D). In the first of these two cases, these vertices actually have r-colours of distinct parities, thus being different, by .

Thus, the r-properness of relies on whether any two vertices at distance at most r from the type-E block and the first-to-last block (of type A or D) have distinct r-colours. Unfortunately, this is not always guaranteed, as this depends on the length of P . Because the consecutive vertices of the type-E block have their r-colours decreasing strictly, is clearly r-proper as soon as the r consecutive vertices v n-r , . . . , v n-2r+1 preceding v n-r+1 also have their r-colours by decreasing strictly (i.e., c

)). This corresponds to situations where v n-r is either the first vertex of a type-A block, or the ith vertex of a type-D block with i ∈ {r + 1, . . . , 2r}. Thus, is r-proper, and χ r Σ (P ) ≤ 3, whenever (n mod 4r + 1) ∈ {r + 1, . . . , 2r + 1}. Particularly, recall that n > 4r + 1, which means that we must have n ≥ 5r + 2 to fall in this case.

Note that the colouring properties obtained in P by applying the previous labelling pattern, are mostly preserved upon starting with assigning label 1 to the first r edges only (and then continuing applying the labelling normally, assigning labelling 3 to the next 2r edges, and so on). By this modified labelling, the main differences are that 1) the vertices of the type-S block verify c r (v 1 ) = r, c r (v 2 ) = r + 3, . . . , c r (v r ) = 4r, and 2) the first type-A block consists of r + 1 vertices only, with r-colours c r (v r+1 ) = 4r + 2, c r (v r+2 ) = 4r + 4, . . . , c r (v 2r+1 ) = 6r. In particular, similarly as with the previous labelling pattern, we might end up with being r-proper if the order of P belongs in a certain range. More precisely, is here r-proper (and, again, χ r Σ (P ) ≤ 3), whenever (n mod 4r + 1) ∈ {1, . . . , r + 1}. Recall again that n > 4r + 1, implying that we have n ≥ 4r + 2 whenever this case applies.

For the remaining values of n, we prove the result in a similar manner, this time applying a different periodic pattern assigning labels 1, 2, 3, 4. Consider first , a 4-labelling of P obtained by applying the consecutive labels 4, . . . , 4, 3, 2, . . . , 2, 4, . . . , 4, 3, 2, . . . , 2, 4, . . . , 4, 3, 2, . . . , 2, 4, . . . , 4, 3, . . . to the edges from first to last, where labels 2 and 4 are assigned to groups of 2r consecutive edges. As previously, we can partition the vertices of P into blocks with certain properties:

8r, and form the type-S block of size r + 1, whose all vertices have even r-colour by ;

• the next 2r vertices v r+2 , . . . , v 3r+1 verify c r (v r+2 ) = 8r -1, c r (v r+3 ) = 8r -3, . . . , c r (v 3r+1 ) = 4r + 1, and form a type-D block of size 2r, whose all vertices have odd r-colour by ;

• the next 2r + 1 vertices v 3r+2 , . . . , v 5r+2 verify c r (v 3r+2 ) = 4r, c r (v 3r+3 ) = 4r + 2, . . . , c r (v 5r+2 ) = 8r, and form a type-A block of size 2r + 1, whose all vertices have even r-colour by ;

• the vertices of P then alternate between type-D blocks and type-A blocks with the same colour properties as above. The last of these blocks is truncated at v n-r and might be of size smaller than intended;