Julien Bensmail

Hervé Hocquard

Dimitri Lajou

On the algorithmic complexity of determining the AVD and NSD chromatic indices of graphs

Keywords: proper edge-colouring, chromatic index, AVD chromatic index, NSD chromatic index

A proper k-edge-colouring φ of a graph G is an assignment of colours from {1, . . . , k} to the edges of G such that no two adjacent edges receive the same colour. If, additionally, φ guarantees that no two adjacent vertices of G are incident to the same sets or sums of colours, then φ is called an AVD or NSD edge-colouring, respectively (the abbreviations AVD and NSD standing for "adjacent vertex distinguishing" and "neighbour sum distinguishing"). The chromatic index χ (G) of G is the smallest k such that proper k-edge-colourings of G exist. Similarly, the AVD and NSD chromatic indices χ AVD (G) and χ NSD (G) of G are the smallest k such that AVD and NSD k-edgecolourings of G exist, respectively. These chromatic parameters are quite related, as we always have

By a well-known result of Vizing, we know that, for any graph G, we must have

In this work, we prove that determining whether a given graph G has AVD or NSD chromatic index ∆(G) is NP-hard for every ∆(G) ≥ 3. We also prove that, for a given graph G, determining whether the AVD or NSD chromatic index is ∆(G) + 1 is NP-hard for every ∆(G) ≥ 3. Through other NP-hardness results, we also establish that there are infinitely many graphs for which the AVD and NSD chromatic indices are different. We actually come up, for every k ≥ 4, with infinitely many graphs with maximum degree k, AVD chromatic index k, and NSD chromatic index k+1, and similarly, for every k ≥ 3, with infinitely many graphs with maximum degree k, AVD chromatic index k + 1, and NSD chromatic index k + 2. In both cases, recognising graphs having those properties is actually NP-hard.

Introduction

For any integer k ≥ 1, a k-edge-colouring φ : E(G) → {1, . . . , k} of a graph G assigns colours from {1, . . . , k} to the edges of G. We say that φ is proper if no two adjacent edges uv and vw (i.e., sharing a vertex v) of G get assigned the same colour by φ. We denote by χ (G) the chromatic index of G, being the smallest k such that proper k-edge-colourings of G exist.

Proper edge-colourings are one of the most central notions of graph theory, due, in particular, to numerous applications. In general, the main question, given a graph G, is to determine χ (G). Surprisingly enough, this question is hard to answer in general, recall the NP-hardness result by Holyer [START_REF] Holyer | The NP-Completeness of Edge-Colouring[END_REF], despite the fact, by a fundamental result of Vizing [START_REF] Vizing | On an estimate of the chromatic class of a p-graph[END_REF], that the chromatic index of a graph is always one of two possible values. Indeed, for a graph G, its chromatic index χ (G) is either ∆(G), the maximum degree of a vertex in G, which stands as the natural lower bound for the parameter, or, at worst, as proved by Vizing, ∆(G) + 1. In the former case, G is said to be of class 1, while it is said to be of class 2 in the latter case. Many interesting works of the literature are precisely on sufficient conditions guaranteeing a graph is of either of these two classes.

Restrictions of proper edge-colourings have also been attracting a lot of attention in the literature. In this area, we are interested in edge-colourings that are not only proper, but also fulfil additional properties. In the context of this paper, we are interested in two such notions, in which it is also required that adjacent vertices get distinguished accordingly to some parameter. The formal definitions are as follows. Let G be a graph, and φ be a proper edge-colouring of G. For every vertex v of G we denote by s(v) the set of colours assigned by φ to the edges incident to v, while we denote by σ(v) the sum of these colours. We say that φ is an AVD edge-colouring if we have s(u) = s(v) for every two adjacent vertices u and v, while we say that φ is an NSD edge-colouring if we have σ(u) = σ(v) for every two adjacent vertices u and v. Lastly, we denote by χ AVD (G) and χ NSD (G) the smallest k such that AVD k-edge-colourings and NSD k-edge-colourings of G exist. We call these parameters the AVD chromatic index and NSD chromatic index of G, respectively.

For reference, let us mention that the terms "AVD" and "NSD" stand for "adjacent vertex distinguishing" and "neighbour sum distinguishing". Note that an NSD edge-colouring must always be an AVD edge-colouring, while the converse does not have to be true. In other words, we have χ NSD (G) ≥ χ AVD (G) for every graph G, while χ AVD (G) ≥ χ (G) since AVD edge-colourings are restrictions of proper edge-colourings. AVD edge-colourings have actually been studied under various names, such as "adjacent strong edge-colourings", "neighbour-distinguishing edge-colourings" and "1-strong edge-colourings". It is worth mentioning that the AVD and NSD chromatic indices are defined for all connected graphs but K 2 ; throughout this paper, we thus implicitly deal only with graphs that do not have K 2 as a connected component.

It is believed that the AVD chromatic index should always be quite close to the chromatic index. This presumption gave birth to the following leading conjecture, raised early in the 2000s: AVD Conjecture (Zhang, Liu, Wang [START_REF] Zhang | Adjacent strong edge coloring of graphs[END_REF]). If G is a connected graph of order at least 6, then χ AVD (G) ≤ ∆(G) + 2.

The NSD chromatic index was introduced more recently, in the 2010s. Due, notably, to connections with the AVD chromatic index, the following was raised: NSD Conjecture (Flandrin, Marczyk, Przybyło, Sacle, Woźniak [START_REF] Flandrin | Neighbor sum distinguishing index[END_REF]). If G is a connected graph of order at least 6, then χ NSD (G) ≤ ∆(G) + 2.

The AVD Conjecture is older than the NSD Conjecture, and, as a result, it has received much more attention to date. Note that these conjectures, if true, would, for each of the AVD and NSD chromatic indices, classify graphs into a small number of classes, just like the chromatic index does. In this work, we say that a graph G is of AVD class 1, 2, or 3, if χ AVD (G) = ∆(G), χ AVD (G) = ∆(G) + 1, or χ AVD (G) = ∆(G) + 2, respectively. Similarly, we say that G is of NSD class 1, 2, or 3, if χ NSD (G) = ∆(G), χ NSD (G) = ∆(G) + 1, or χ NSD (G) = ∆(G) + 2, respectively.

Most of the works done so far on the topic have been dedicated to proving the AVD and NSD Conjectures for various classes of graphs, and sometimes to going even further by establishing conditions for graphs to be of AVD or NSD class 1 or 2. For a recent survey, we refer the reader to [START_REF] Hocquard | On various problems related to edge-colorings[END_REF][START_REF] Lajou | On various graph coloring problems[END_REF], in which most of the works done on the topic to date have been summarised.

Our investigations in this work stem from legitimate questions one could ask regarding the connections between the AVD and NSD chromatic indices of graphs. These two notions, due to the definitions involved, are undoubtedly very close, and, as a matter of fact, most of the previous works on the topic have actually dealt with these two notions as nearly similar ones. It is far less clear, however, what the general discrepancies between the AVD and NSD chromatic indices are. As made apparent in the definitions, an NSD edge-colouring is always an AVD edge-colouring, and χ NSD (G) ≥ χ AVD (G) thus always holds for a graph G. It is not obvious, however, whether we always have χ NSD (G) = χ AVD (G). One could think that, perhaps, especially when ∆(G) is large, it could be that any graph G always admits so many AVD χ AVD (G)-edge-colourings that one of them must be an NSD edge-colouring. It is worth adding that examining small graphs does not allow to come up with an obvious counterexample to that presumption.

Our first intuitions on that question were inspired from [START_REF] Bensmail | On proper 2-labellings distinguishing by sums, multisets or products[END_REF], in which similar questions were answered for non-proper versions of AVD and NSD edge-colourings. In brief, therein, the authors consider k-labellings, which are, essentially, k-edge-colourings (no properness condition is required whatsoever). The goal, given a graph G, is to determine χ M (G) and χ S (G), which are the smallest k such that k-labellings distinguishing any two adjacent vertices through their multisets and sums of incident labels exist, respectively. Note that the parameters χ M and χ S do stand as non-proper versions of χ AVD and χ NSD . In particular, χ S (G) ≥ χ M (G) holds for any graph G. Similarly as for the AVD and NSD chromatic indices, a question was then whether we always have χ S (G) = χ M (G).

In [START_REF] Bensmail | On proper 2-labellings distinguishing by sums, multisets or products[END_REF], the authors answered this question negatively, showing that, for a graph G with χ M (G) = 2, it is NP-hard to decide whether χ S (G) = 2. This shows that there exist infinitely many graphs G with χ M (G) = χ S (G). The authors also discussed the structure of these graphs, which seem to be rather large in general, justifying why spotting a single one did not seem obvious at first.

These considerations led us to realising a surprising fact, being that we were not able to come up with any reference of the literature discussing the complexity of determining the AVD and NSD chromatic indices of graphs. There is of course a chance that we just missed such a reference, especially when taking into account, as mentioned earlier, that the literature on the topic is far from being uniform, many notions being reintroduced and investigated under different names. Still, complexity aspects, especially when it comes to colouring problems, are fundamental aspects, and we would thus be surprised if something was known but not mentioned in any on the latest works on the topic. One of our additional motivations in this work, is thus to provide hints on the complexity of determining the AVD and NSD chromatic indices of a given graph. It is worth mentioning that, in any case, the main results we prove in this work, on the existence of graphs for which the AVD and NSD chromatic indices differ, are actually intimately related to those complexity questions.

In this work, we thus provide results regarding two different questions. Using graphs with particular colouring properties introduced in Section 2, we first establish, in Section 3, that determining whether a given graph with maximum degree k is of AVD or NSD class 1 or 2, is NP-hard1 for every2 k ≥ 3. Then, in Section 4, we prove that there exist infinitely many graphs with maximum degree k of AVD class 1 and NSD class 2 (which we prove for every k ≥ 4, which is best possible), and similarly infinitely many graphs with maximum degree k of AVD class 2 and NSD class 3 (which we prove for every k ≥ 3). This is done mainly by refining our NP-hardness proofs from Section 3, by making sure to design reduced graphs with certain edge-colouring properties. Thus, not only infinitely many graphs with differing AVD and NSD chromatic indices exist, but also recognising them is NP-hard. Let us emphasise that our results are thus on very particular aspects of AVD and NSD edge-colourings, which, consequently, do not bring much on the main open questions of the field, being the AVD and NSD Conjectures. We end up this work in Section 5, in which we comment on these results, and suggest additional questions for further work on this topic.

Some gadgets and their edge-colouring properties

In many complexity results dealing with edge-colourings, one of the most important points is designing forcing mechanisms. That is, in order to design an NP-hardness reduction for some edgecolouring problem, the first step is often to come up with graphs (gadgets) for which all certain edge-colourings behave in a very anticipated way. This can concern e.g. the fact that certain edges must always be assigned the same colour or pairwise distinct colours, or the fact that certain vertices must be incident to edges being assigned certain colours. Our main results in this work deal precisely with such forcing mechanisms. For this reason, it is not surprising that some notions and gadgets introduced through what follows are, in spirit at least, reminiscent of ones designed for related different problems (such as those from [START_REF] Bensmail | On proper 2-labellings distinguishing by sums, multisets or products[END_REF]).

The main gadgets to be used in our reductions in the next sections build upon the following construction (see Figure 1(a) for an illustration3 ). Definition 2.1 (Gadget M k ). For any k ≥ 2, the graph M k is obtained as follows. Start from the complete bipartite graph K k-1,k with bipartition U ∪ V , where U = {u 0 , . . . , u k-2 } and V = {v 0 , . . . , v k-1 }, and add an edge v i w i for every i ∈ {0, . . . , k -1}, where w i is a new degree-1 In each case, is also given an AVD edge-colouring using the least number of colours possible (4 in (a), 5 in (b)). In (a), the set of incident colours is given for every vertex of maximum degree [START_REF] Hocquard | On various problems related to edge-colorings[END_REF]. Note also that, in (b), the edges of the four copies of M 4 are not coloured the same way, to illustrate the fact that, in an AVD 5-edge-colouring of G 4,4 , even though we have some control over the sets of incident colours achieved for the support vertices, we have less control on how those sets are obtained.

u 0 u 1 v 0 v 1 v 2 w 0 w 1 w 2 (a) M 3 (b) G 4,4
vertex. The resulting graph is M k . Note that the k edges v 0 w 0 , . . . , v k-1 w k-1 of M k are pending edges (i.e., edges incident to a degree-1 vertex); we call these edges the outputs of M k , the w i 's being their ends.

M k has several colouring properties of interest, due, in particular, to its structure and to the degrees of its vertices, which make the following obvious observation (to be used implicitly throughout this work) applicable. Observation 2.2. Let G be a graph, and φ be a proper edge-colouring of G. If u and v are two adjacent vertices of G with d(u) = d(v), then s(u) = s(v).

Theorem 2.3. For every k ≥ 2, the graph M k fulfils the following:

• ∆(M k ) = k. • χ AVD (M k ) = k + 1.
• By every AVD (k + 1)-edge-colouring of M k , the k outputs must be assigned the same colour.

• There is an AVD (k + 1)-edge-colouring of M k such that s(u i ) = {1, . . . , k} for every i ∈ {0, . . . , k -2} and s(v i ) = {1, . . . , k + 1} \ {i + 1} for every i ∈ {0, . . . , k -1}.

• Every AVD (k + 1)-edge-colouring of M k is also an NSD (k + 1)-edge-colouring. Thus, χ NSD (M k ) = k + 1, and, by every NSD (k + 1)-edge-colouring of M k , the k outputs must be assigned the same colour. Also, there is an NSD

(k + 1)-edge-colouring of M k such that σ(u i ) = k(k+1) 2 for every i ∈ {0, . . . , k -2} and σ(v i ) = (k+1)(k+2) 2 -(i + 1) for every i ∈ {0, . . . , k -1}.
Proof. The first item follows from the construction of M k . Regarding the second and third items, we note first that we have χ AVD (M k ) ≥ k + 1 since the u i 's and v i 's all have degree k and are adjacent. We claim that we also have χ AVD (M k ) ≤ k + 1, and, in particular, that by all AVD (k + 1)-edge-colourings of M k , the condition of the third item must be met.

• First off, we claim that an AVD (k + 1)-edge-colouring φ of M k is obtained when colouring the edges of M k in the following way. We consider the u i 's one after another. Whenever considering u i for some i ∈ {0, . . . , k -2}, we simply set φ(u i v i+j mod k ) = (j mod k) + 1 for every j ∈ {0, . . . , k -1}. To make it more precise, note that, for u 0 , this results in φ(u 0 v j ) = j + 1 for every j ∈ {0, . . . , k -1}. For u 1 , this results in φ(u 1 v 0 ) = k and φ(u 1 v j ) = j for every j ∈ {1, . . . , k -1}. In other words, for every u i , we assign colours 1, . . . , k to the edges u i v i , u i v i+1 , . . . u i v i+k-1 following that order, taking into account that the operations over the subscripts are modulo k.

Note that, at this point, this colouring pattern clearly results in φ being a partial proper edge-colouring. Also, we currently have s(u i ) = {1, . . . , k} for every i ∈ {0, . . . , k -2}, as well as s(v i ) = {1, . . . , k} \ {i + 1} for every i ∈ {0, . . . , k -1}. To finish off the construction of φ, we just consider every i ∈ {0, . . . , k -1}, and set φ(v i w i ) = k + 1. As a result, every u i still satisfies s(u i ) = {1, . . . , k}, while every

v i now satisfies s(v i ) = {1, . . . , k + 1} \ {i + 1}.
Thus, the u i 's and v i 's cannot be in conflict, and the w i 's also cannot be in conflict with the v i 's, their degree being 1. Note that φ actually fulfils the property described in the fourth item. The existence of φ also proves the second item of the statement.

• We now focus on the third item of the statement. Consider an AVD (k + 1)-edge-colouring φ of G. For every vertex x ∈ {u 0 , . . . , u k-2 , v 0 , . . . , v k-1 }, note that there is exactly one colour in {1, . . . , k + 1}, which we denote by m(x), that is not assigned to any of the k edges incident to x. Without loss of generality, we may assume that all colours in {2, . . . , k + 1} are assigned to edges incident to v 0 , i.e., m(v 0 ) = 1. This implies that m(u i ) = 1 for every i ∈ {0, . . . , k -2} (as otherwise we would have a set conflict contradicting that φ is an AVD edge-colouring). Since no u i can miss colour 1, we can suppose without loss of generality that φ(u i v i+1 ) = 1 for every i ∈ {0, . . . , k -2}. This implies that for every i ∈ {1, . . . , k -1}, m(v i ) = 1. By applying a similar argument to the other v i 's, we obtain that no two v i miss the same colour. Without loss of generality, we can suppose that m(v i ) = i + 1 for every i ∈ {0, . . . , k -1}. Hence, we deduce that m(u i ) = k + 1 for every i ∈ {0, . . . , k -2}. Now, for every i ∈ {0, . . . , k -1}, we have m(v i ) = k + 1, and thus v i is incident to an edge coloured k + 1. Note that, that edge cannot be of the form v i u j since m(u j ) = k + 1 for every j ∈ {0, . . . , k -2}. This implies that φ(v i w i ) = k + 1 for every i ∈ {0, . . . , k -1}.

Regarding the fifth item, notice that, indeed, an AVD (k + 1)-edge-colouring φ of M k must be an NSD edge-colouring, as degree-1 vertices cannot be involved in sum conflicts, and all u i 's and v i 's have degree k. In particular, every u i or v i has sum (k+1)(k+2) 2 -α for some α ∈ {1, . . . , k + 1}. From this, we deduce that having σ(u i ) = σ(v j ) for some u i and v j would imply that s(u i ) = s(v j ), a contradiction to φ being an AVD edge-colouring. From these arguments, the rest of the fifth item follows directly from the other items of the statement.

We now consider the following construction, which consists essentially in connecting several copies of some M k in a sequential way, resulting in a path-like graph G k,r (see Figure 1

(b)). Definition 2.4 (Gadget G k,r ). Let k ≥ 3 and r ≥ 1 be fixed. The graph G k,r is obtained as follows. Start from r disjoint copies G 1 , . . . , G r of M k . Since k ≥ 3,
recall that each G i has at least three outputs. For each i ∈ {1, . . . , r}, we choose three arbitrary outputs of G i , which we denote by e i , f i , g i . We now consider every i ∈ {1, . . . , r -1} in turn, and identify the edges f i and e i+1 so that the maximum degree of the resulting graph remains k. More formally, for some i, if we denote f i = uv and e i+1 = xy so that v and x are the two ends, then identifying f i and e i+1 essentially means identifying u and x, identifying v and y, and making sure to keep the graph simple. The resulting graph is G k,r . The r pending edges g 1 , . . . , g r of G k,r are called its outputs. Furthermore, for every output g i , we call its degree-1 vertex an end (that of g i being the ith one) while we call its other vertex a support (being the ith one, w.r.t. g i ).

It is important to emphasise that G k,r does have r outputs only, while it might have much more pending edges, in particular when k and r are large, most of which are not defined as outputs. Note also that the construction above introduces the edges e 1 and f r of G k,r , which actually serve no purpose other than making the description above more general and easier to give.

Colouring properties of M k extend to G k,r ; namely:

Theorem 2.5. For every k ≥ 3 and r ≥ 1, the graph G k,r fulfils the following:

• ∆(G k,r ) = k. • χ AVD (G k,r ) = k + 1.
• By every AVD (k + 1)-edge-colouring of G k,r , the r outputs must be assigned the same colour.

• For any r subsets F 1 , . . . , F r of cardinality k of {1, . . . , k + 1}, there is an AVD (k + 1)-edgecolouring of G k,r such that for every ith support x we have s(x) = F i .

• Every AVD (k + 1)-edge-colouring of G k,r is also an NSD (k + 1)-edge-colouring. Thus, χ NSD (G k,r ) = k + 1, and, by every NSD (k + 1)-edge-colouring of G k,r , the r outputs must be assigned the same colour. Also, for any r positive integers f 1 , . . . , f r , there is an NSD (k + 1)-edge-colouring of G k,r such that for every ith support x we have σ(x) = f i .

Proof. The first item follows from the construction of G k,r . Also, because G k,r contains M k as a particular induced subgraph, we have ), the set of colours incident to x by φ 1 is different from the set of colours incident to y by φ 2 . Repeating these arguments to G 3 , . . . , G r one after another, we deduce AVD (k + 1)-edge-colourings φ 1 , . . . , φ r of G 1 , . . . , G r , respectively, which, when combined, yield one of G k,r fulfilling the property of the fourth item. This also proves that χ AVD (G k,r ) ≤ k + 1, thus the second item.

χ AVD (G k,r ) ≥ χ AVD (M k ) ≥ k + 1 (
The third item follows from the fact that an AVD (k +1)-edge-colouring of G k,r , when restricted to the edges of the G i 's, must yield AVD (k + 1)-edge-colourings of G 1 , . . . , G r . The third item of Theorem 2.3 thus implies the third item of the current statement.

The last item follows from the fact that all vertices of G k,r have degree 1 or k. In particular, because G k,r does not have adjacent vertices of degree 1, and (k + 1)-edge-colourings assign strictly positive colours, by such an edge-colouring a degree-1 vertex can never be incident to the same sum of colours as its unique neighbour. Regarding any two adjacent vertices u and v of degree k, note that, by an AVD (k + 1)-edge-colouring φ of G k,r , we always have s(u) = {1, . . . , k + 1} \ {α} and s(v) = {1, . . . , k + 1} \ {β}, for some α = β (as otherwise we would have s

(u) = s(v)). This means that σ(u) = (k+1)(k+2) 2 -α and σ(v) = (k+1)(k+2) 2 -β, thus, since α = β, that σ(u) = σ(v).
From this, we get that φ is also an NSD (k + 1)-edge-colouring of G k,r . These arguments, and the other items we have proved, show that G k,r fulfils all the properties of the last item.

In later proofs, we will repeatedly use the fact that certain edge-colourings of G k,r must all have particular properties, in particular regarding their outputs and support vertices. To exploit this, we will manipulate G k,r through the next two operations (see Figure 2).

Definition 2.6 (Connection operation).

Let G be a graph with p pending edges e 1 = v 1 u 1 , . . . , e p = v p u p where d(u i ) = 1 for every i ∈ {1, . . . , p}, the v i 's are pairwise different, and d(v i ) ≥ 2 for every i ∈ {1, . . . , p}. By connecting e 1 , . . . , e p to x we mean identifying all of u 1 , . . . , u p to a single vertex x. Definition 2.7 (Attachment operation). Let G be a graph with a pending edge e = vu where d(u) = 1, and let w ∈ N (v) be another vertex of G. By attaching u at w we mean identifying u and w.

1 v 2 v p u 1 u 2 u p v 1 v 2 v p x (

Base reductions

We start by proving that deciding whether a given graph is of AVD class 1 is an NP-hard problem. We actually prove a stronger result, namely that this remains true when restricted to graphs with maximum degree k for every k ≥ 3. Theorem 3.1. For every k ≥ 3, it is NP-hard to decide whether a given graph with maximum degree k is of AVD class 1.

Proof. Let k ≥ 3 be fixed. We prove the result by reduction from the problem of determining whether a given k-regular graph is of class 1 (w.r.t. the chromatic index), which is known to be NP-hard [START_REF] Leven | NP Completeness of Finding the Chromatic Index of Regular Graphs[END_REF]. That is, given a k-regular graph G, we construct, in polynomial time, a graph H with maximum degree k, such that χ (G) = k if and only if χ AVD (H) = k.

The construction of H is achieved starting from G, by replacing every edge of G by a copy of M k-1 (which is well defined, since k ≥ 3). More formally, we consider every edge e = uv of G in turn, remove e from the graph, add a new copy G e of M k-1 , choose any two outputs wx and yz of G e where w and z are the ends, and identify w and u, and similarly z and v. Note that, in H, the original vertices (from G) are still of degree k, while all other vertices (from the G e 's) have degree k -1 or 1. Thus, H has maximum degree k, and it is clearly obtained in polynomial time.

We now prove that we have the desired equivalence between G and H:

• Assume first that H admits an AVD k-edge-colouring φ. By Theorem 2.3, recall that, for each copy G e of M k-1 , by φ all outputs must be assigned the same colour. Let thus φ be the k-edge-colouring of G obtained by considering every edge e ∈ E(G) and setting φ (e) = x, where x is the colour assigned by φ to all outputs of G e in H. We claim that φ is proper. Take two incident edges of G, say uv and uw. By construction, one output of G uv in H and one output of G uw in H is incident with u, forcing that the outputs of G uv and G uw have different colors in φ . Therefore, by construction, uv and uw have different colors in the edge-coloring φ.

• Assume now that G admits a proper k-edge-colouring φ. To obtain an AVD k-edge-colouring φ of H, we consider every edge e = uv of G in turn, assign colour φ(e) by φ to the exactly two edges (actually outputs) of G e incident to u and v, and extend this pre-colouring of G e in an AVD way to all its edges, which is possible according to Theorem 2.3. The fact that the resulting φ is indeed an AVD edge-colouring of the whole of H, follows from the fact that, generally speaking, for two vertices to have the same set of incident colours, they must be of the same degree. Note that, in H, all adjacent vertices with the same degree belong to the G e 's, and they have degree precisely k -1. By how φ was obtained, in particular through Theorem 2.3 to colour the edges of the G e 's, we deduce that there cannot be set conflicts.

Note that, in the proof of Theorem 3.1, the graphs H of maximum degree k we construct have all their vertices being of degree k, k -1, or 1. By any proper k-edge-colouring, note that a vertex v of degree k verifies σ

(v) = k(k+1) 2 . Similarly, a vertex v of degree k -1 verifies σ(v) = k(k+1)

2

-α where α ∈ {1, . . . , k} is the only colour not assigned to an edge incident to v. Note also that since we are assigning strictly positive integers as colours, a degree-1 vertex cannot get the same sum of incident colours as its unique neighbour, unless the graph is K 2 . From all these arguments, we deduce that any AVD k-edge-colouring of H in the proof of Theorem 3.1 is also an NSD k-edge-colouring. This implies the following: Theorem 3.2. For every k ≥ 3, it is NP-hard to decide whether a given graph with maximum degree k is of NSD class 1.

We now prove similar results for graphs of AVD and NSD class 2. It is important to emphasise, at this point, that the NP-hardness reduction we give in the proof of the next result will be the starting point for the proofs of most of our main results in later sections. Theorem 3.3. For every k ≥ 3, it is NP-hard to decide whether a given graph with maximum degree k is of AVD class 2.

Proof. Let k ≥ 3 be fixed. The result follows from the reduction below, from the problem of determining whether a given graph G has chromatic number χ(G) = k + 1 (which is NP-hard since k + 1 ≥ 4 is fixed, see [START_REF] Karp | Reducibility among Combinatorial Problems[END_REF]), i.e., admits proper (k + 1)-vertex-colourings, that is, partitions of its vertex set V (G) into k + 1 stable sets (i.e., sets in which no two vertices are adjacent). Given a graph G, we construct, in polynomial time, a graph H with maximum degree

∆(H) = k such that χ(G) = k + 1 if and only if χ AVD (H) = k + 1.
We construct H as follows (see Figure 3). Set D = ∆(G). For every vertex v of G, we add, in H, a copy G v of G k,D . Now, for every edge uv of G, we connect, in H, a new output of G u and and a new output of G v . By "new output", we mean that every output of any G v must be involved, through the whole construction, in at most one output connection. That is, any vertex of H resulting from some identification (through some output connection) must be of degree precisely 2.

Clearly, H is obtained in polynomial time from G. Also, H being obtained by connecting disjoint outputs of copies of G k,D , its maximum degree is precisely k. Actually, the vertices of H have degree k (non-end vertices), 2 (identified ends), or 1 (non-identified ends).

Let us prove that we have the desired equivalence.

• Assume first that G admits a proper (k + 1)-vertex-colouring φ. Let us consider the (k + 1)edge-colouring φ of H obtained by simply considering an AVD (k + 1)-edge-colouring φ v of every G v where all outputs are assigned colour φ(v) (such an edge-colouring of G v exists by Theorem 2.5), and combining all φ v 's to form φ . Clearly, all edges of H get assigned a colour by φ . For every edge uv of G, note that, in H, the only two adjacent edges of G u and G v must be assigned distinct colours by φ , since we have φ(u) = φ(v). This, and the fact that the φ v 's are AVD edge-colourings, imply that φ is proper. The fact that φ is also an AVD edge-colouring is because any two adjacent vertices of degree k from some G v cannot be in conflict since φ v was obtained through Theorem 2.5. So the only possible conflicts involve ends, which are of degree at most 2 while their neighbours (which are part of the G v 's) are of degree k ≥ 3; thus, here as well, we cannot have set conflicts.

• Assume now that H admits an AVD (k + 1)-edge-colouring φ. By Theorem 2.5, all outputs of any G v must be assigned the same colour by φ, and, for φ to be proper, any G u sharing an end with G v cannot have its outputs being assigned the same colour as that assigned to the outputs of G u . It follows that the (k + 1)-vertex-colouring φ of G where every vertex v is assigned, by φ , the colour assigned by φ to the outputs of G v in H, is proper.

Again, we note that the reduction in the proof of Theorem 3.3 also applies to NSD (k + 1)edge-colourings. Namely, in the graphs H we construct, vertices have degree k, 2, or 1. Recall that vertices of degree 1 cannot have the same sum of incident colours as their unique neighbour, unless the graph is K 2 . By how AVD (k + 1)-edge-colourings are obtained in the proof, vertices of degree k have sum (k+1)(k+2) 2 -α for some α ∈ {1, . . . , k + 1}, any two adjacent vertices of degree k missing different α's as otherwise their sets of incident colours would be the same. Note also that H does not have two adjacent vertices of degree 2. Actually, the last possible sum conflicts are between degree-2 vertices and degree-k vertices. Note that the largest possible sum for a degree-2 vertex by a proper (k + 1)-edge-colouring is k + k + 1 = 2k + 1, while the smallest possible sum for a degree-k vertex is k(k+1)

2

. When k ≥ 4, note that we always have k(k+1) 2 > 2k + 1, and thus such sum conflicts cannot occur. For the case k = 3, note that, to avoid conflicts between a degree-3 vertex x and a degree-2 vertex y, we can invoke the fifth item of Theorem 2.5 to make sure that, by AVD 4-edge-colourings of the G v 's, in H the resulting sum of colours incident to x (which is the support of some G v ) is different from that to y. Thus, the following also holds: Theorem 3.4. For every k ≥ 3, it is NP-hard to decide whether a given graph with maximum degree k is of NSD class 2.

Enhanced reductions

In this section, we build upon the reduction in the proof of Theorem 3.3 to prove that determining the AVD chromatic index of a graph is NP-hard even when its NSD chromatic index is fixed, and vice versa. As a side result, we thus get that there are infinitely many graphs G such that χ AVD (G) < χ NSD (G); actually, recognising such graphs cannot be done in polynomial time, unless P=NP.

We begin by raising and recalling a few preliminary facts. Proof. Assume G admits an AVD 3-edge-colouring φ. We claim that φ is an NSD edge-colouring. Indeed, let us consider the possible sets (and sums) of colours incident to any vertex v of G: Assume we have σ(u) = σ(v) for some edge uv of G. If d(u) = d(v), then note that, by the classification above, we must have s(u) = s(v), a contradiction to φ being an AVD edge-colouring. Now, if d(u) = d(v), then, still by the classification above, we must have σ(u) = σ(v) = 3, which occurs only when, say, d(u) = 2 and d(v) = 1. More precisely, the only edge incident to v must be assigned colour 3 by φ, while the two edges incident to u must be assigned colours 1 and 2. This is clearly impossible, since u and v are adjacent. So, φ must be an NSD 3-edge-colouring. Lemma 4.2. For every k ≥ 3, it is NP-hard to decide whether a given graph

• if d(v) =
G with χ(G) ≤ k + 1 verifies χ(G) = k.
Proof. This follows from the fact that, for every k ≥ 3, it is NP-hard to decide whether a k-regular graph H is of class 1 (recall [START_REF] Leven | NP Completeness of Finding the Chromatic Index of Regular Graphs[END_REF]). Indeed, recall that χ (H) ∈ {k, k +1} by Vizing's Theorem, and, in particular, that proper (k + 1)-edge-colourings of H always exist [START_REF] Vizing | On an estimate of the chromatic class of a p-graph[END_REF]. Now consider G = L(H), the line graph of H (edges of H become vertices of G, every two of which are adjacent if and only if the corresponding two edges of H are adjacent). It is well known that finding a proper edge-colouring of H is exactly equivalent to finding a proper vertex-colouring of G. In particular, G is properly (k + 1)-vertex-colourable, and finding a proper k-vertex-colouring of G is equivalent to finding a proper k-edge-colouring of H. The result thus follows, since constructing the line graph of any given graph can clearly be done in polynomial time.

We are now ready to prove our main results in this section.

Determining χ AVD when χ NSD is fixed

Recall that the next result does not hold for k = 3, because of Observation 4.1.

Theorem 4.3. For every k ≥ 4, it is NP-hard to decide whether a given graph of NSD class 2 with maximum degree k is of AVD class 1.

Proof. Let k ≥ 4 be fixed. We prove the result by reduction from the problem of deciding whether a given graph that is properly k-vertex-colourable is properly (k -1)-vertex-colourable (which is NP-hard by Lemma 4.2, since k ≥ 4). Given a graph G that is properly k-vertex-colourable, we construct, in polynomial time, a graph H of NSD class 2 with maximum degree

∆(H) = k such that G is properly (k -1)-vertex-colourable if and only if H is of AVD class 1.
We construct H as follows (see Figure 4). Start from k copies G 1 , . . . , G k of G k-1,r (which is well defined, since k ≥ 4). The value of r we need will be clarified as the construction is achieved; for now, let us assume that r is sufficiently large so that we always have a new output of any G i in hands whenever we need one. Consider now k outputs e 1 , . . . , e k of the G i 's, where every e i is an output of G i , and connect e 1 , . . . , e k to a vertex x. Next, for every three pairwise distinct integers i, j, ∈ {1, . . . , k}, take one new output e of G i , one new output f of G j , and one new output g of G k , connect e and f to a vertex u i,j, , and, denoting v i,j, the end of g, add the edge u i,j, v i,j, .

Reduced graph from Theorem 3.3 Wiggly edges are outputs of some G k,r . Due to space limitation, note that not all pairs {u i,j, , v i,j, } are represented.

G a G b G1 G2 G3 G4 x u 1,2,3 v 1,2,3 u 1,3,4 v 1,3,4
To end up the construction of H, we now proceed similarly as in the reduction in the proof of Theorem 3.3. That is, assuming4 D = ∆(G), for every vertex v of G we add a copy G v of G k-1,D+1 (which, again, is well defined) to the graph, and for every edge uv ∈ E(G) we connect an output of G u and an output of G v . Lastly, for every G v , we connect an output of G v and an output of G 1 .

Note that, for any G i , the value of r we need is bounded above by 1 + k 3 + |V (G)|: one output is used for creating x, at most k 3 outputs are used to create u i,j, 's and v i,j, 's, and |V (G)| outputs might be connected to outputs of the G v 's. Thus, H is obtained in polynomial time.

Note also that H is of maximum degree exactly k: vertex x is of degree exactly k, while it can be checked that, by construction, every other vertex has degree at most k -1. We claim also that H is of NSD class 2. Indeed, assume, towards a contradiction, that H admits an NSD k-edge-colouring φ. By Theorem 2.5, every G i must have all its outputs being assigned the same colour by φ since ∆(G i ) = k -1. Since all the G i 's have an output incident to x, we deduce that some G i must have all its outputs assigned colour 1 by φ, and similarly some G j and G (with i, j, being pairwise distinct) must have all their outputs assigned colours 2 and 3 by φ, respectively. But then we deduce that σ(u i,j, ) = σ(v i,j, ) = 3 + φ(u i,j, v i,j, ), a contradiction.

To see now that H admits NSD (k + 1)-edge-colourings, one can consider e.g. the following construction for an edge-colouring φ of H. Start by edge-colouring every G i in an NSD way with only colours 1, . . . , k. As mentioned earlier, we may assume that G i has all its outputs assigned colour i for every i ∈ {1, . . . , k}. Now, consider every u i,j, , and change to k + 1 the colour assigned by φ to the output of G i incident to u i,j, . Note that this raises no properness issues. In particular, we always have σ(u i,j, ) > σ(v i,j, ) since u i,j, is incident to an edge with colour k + 1 while v i,j, is not, and d(u i,j, ) = 3 > 2 = d(v i,j, ). Now, assign a valid colour to every edge u i,j, v i,j, so that the resulting edge-colouring remains proper and no sum conflicts arise. Note that this is always possible, as only three colours are forbidden for every edge u i,j, v i,j, due to the properness requirement, while, regarding the sum requirement, by the fifth item of Theorem 2.5 we can freely modify (if needed) the edge-colourings of the G i 's so that the supports of the outputs incident to the u i,j, 's have the largest sum possible, to guarantee they cannot be involved in sum conflicts with their neighbours in the G i 's. We now extend φ to the G v 's. For that, we consider ψ, a proper {2, . . . , k + 1}-vertex-colouring of G, which exists by our original hypothesis on G. We consider now every G v , and extend φ to its edges in an NSD way with colours 2, . . . , k + 1 in such a way that all its outputs are assigned colour ψ(v) (this can be done starting from an NSD k-edge-colouring, by eventually adding 1 to all assigned colours). Note that we do not get properness issues, because ψ is a proper vertex-colouring of G and no G v has its outputs assigned colour 1 (recall indeed that every G v has an output connected to an output of G 1 , which has its outputs assigned colour 1). Furthermore, the fact that we assign colours in {2, . . . , k + 1}, because in the G v 's all vertices have degree k -1, has no impact on the fact that every G v can be edge-coloured so that sum conflicts are avoided around the outputs, as described in the fifth item of Theorem 2.5. All in all, we can thus obtain an NSD (k + 1)-edge-colouring of H, which shows that it is of NSD class 2.

We claim that we also have the desired equivalence between G and H:

• Assume H is of AVD class 1, i.e., H admits an AVD k-edge-colouring φ. By Theorem 2.5, all outputs of G 1 must be assigned the same colour by φ. Without loss of generality, we may assume that colour is k. Similarly, all G v 's have their outputs assigned the same colour, and no G v can assign colour k to its outputs due to a connection with G 1 . Also, by construction, if uv ∈ E(G), then G u and G v share an end in H, and thus they cannot assign the same colour to their outputs by φ. It follows that the (k -1)-vertex-colouring φ of G, obtained by setting φ (v) = α for every v ∈ V (G), where α is the colour assigned by φ to the outputs of G v , is a proper (k -1)-vertex-colouring of G.

• Assume now that G admits a proper (k -1)-vertex-colouring φ. Free to rename the colours, we can assume φ is a {2, . . . , k}-vertex-colouring. To obtain an AVD k-edge-colouring φ of H, we can proceed as earlier. Start from an AVD k-edge-colouring of every G i where all outputs are assigned colour i (which exists, by Theorem 2.5). Note that, this far, no properness issues are raised, the u i,j, 's and v i,j, 's cannot be in set conflicts due to their degrees being different, and, by conveniently choosing set colours through the fourth item of Theorem 2.5, we can make sure no other set conflicts involve ends of the G i 's. Now extend φ in an AVD way to the G v 's with making sure that all outputs of any G v are assigned colour φ(v), and so that no set conflicts arise around the outputs. This is possible, still by the fourth item of Theorem 2.5. Now, since φ is a proper vertex-colouring of G, and G 1 has all its outputs assigned colour 1 while none of the G v 's has this property, we deduce that φ must be an AVD k-edge-colouring of H. Hence, H is of AVD class 1.

Theorem 4.4. For every k ≥ 3, it is NP-hard to decide whether a given graph of NSD class 3 with maximum degree k is of AVD class 2.

Proof. Let k ≥ 3. This result can be proved through a reduction quite similar to that in the proof of Theorem 4.3, the main differences being the following:

• The reduction is from the problem of deciding whether a given properly

(k + 1)-vertex- colourable graph G is properly k-vertex-colourable.
Recall that this problem is indeed NPhard by Lemma 4.2, since k ≥ 3.

• In H, we now have k + 1 G i 's, G 1 , . . . , G k+1 , which are here copies of G k,r .

• Instead of connecting outputs of the G i 's to the single vertex x, we now connect them in pairs. That is, for every two distinct i, j ∈ {1, . . . , k + 1}, we connect one output of G i and one output of G j to a vertex x i,j .

• The G v 's are copies of G k,r .

The rest of the reduction is similar. In particular, for every pairwise distinct i, j, ∈ {1, . . . , k + 1} we create and join the vertices u i,j, and v i,j, as previously, and we create the G v 's from G, which are all connected to G 1 and connected in pairs following the structure of G.

Note that the modifications above have no impact on the fact that the reduction is performed in polynomial time. The most important difference is that the maximum degree of H is k, which is the maximum degree of the vertices in the G i 's (and G v 's). From the second item of Theorem 2.5, we thus deduce that χ NSD (H) ≥ χ AVD (H) ≥ k + 1. Now, note that by an AVD (k + 1)-edge-colouring of H, we still have the property that all G i 's (and G v 's) must have all their outputs assigned the same colour, and that any two of the G i 's cannot assign the same colour to their outputs because of the x i,j 's. From these arguments, we essentially get that an AVD or NSD (k + 1)-edge-colouring of H here, behaves similarly as an AVD or NSD k-edge-colouring of H as constructed in the proof of Theorem 4. Before we start describing H, let us first introduce some graph Q, which is reminiscent of graphs we have already constructed in previous proofs, and which will be needed for constructing H. We start from k copies G 1 , . . . , G k of G k-1,r for r large enough. Again, we consider e 1 , . . . , e k , any k outputs of the G i 's, where e i is an output of G i for every i ∈ {1, . . . , k}, and connect e 1 , . . . , e k to a vertex x. Next, for every two distinct integers i, j ∈ {2, . . . , k}, we consider one new output e of G 1 , one new output f of G i , and one new output g of G j , connect e and f to a vertex u i,j , and, denoting v i,j the end of g, add the edge u i,j v i,j . The resulting graph is Q (depicted in Figure 5(a))

G1 G2 G3 G4 x u 2,3 v 2,3 u 3,4 v 3,4 (a) Gadget Q Reduced graph from Theorem 3.3 G a G b Q a Q b (b) Attaching copies of Q
We are now ready to construct H (see Figure 5(b)). Set D = ∆(G). We start by considering every vertex v of G, and add, to H, a copy G v of G k-1,D+1 . Now, for every edge uv of G, we connect a new output of G u and a new output of G v in H. Lastly, for every vertex v of G, we add a copy Q v of Q to H, and connect a new output of the G 1 in Q v and a new output of G v .

It can be checked that H, which is clearly constructed in polynomial time, has maximum degree exactly k, due notably to x. For the same reasons as in the proof of Theorem 4.3, there exist AVD k-edge-colourings of Q. Precisely, in Q, all G i 's must have their outputs being assigned the same colour, and, because of x, no two of the G i 's can share the same colour on their outputs. Also, the u i,j 's and v i,j 's are of different degrees (3 and 2, respectively), while their neighbours have degree at least 3. By the fourth item of Theorem 2.5, we can avoid any set conflict between u i,j and its two neighbours in G 1 and G i , by conveniently choosing the set of colours incident to these two vertices, which can be done at will. This implies that, when colouring any edge u i,j v i,j , we only have to care about properness, which is fine since we have at least four colours in hands. Now, to construct an AVD k-edge-colouring of H, one can proceed as follows. Let ψ be a proper k-vertexcolouring of G, which exists by our assumption on G. For every vertex v of G, start, as in the proof of Theorem 4.3, by k-edge-colouring G v in an AVD way so that the outputs are assigned colour ψ(v), which is possible according to Theorem 2.5. Note that for every two adjacent vertices u and v of G, the connected outputs of G u and G v in H receive distinct colours by the edge-colouring, as ψ(u) = ψ(v). Also, any vertex resulting from the connection of some G u and G v has degree 2 while its neighbours have degree at least 3, and thus we cannot have set conflicts involving such vertices. Lastly, we consider every Q v , and extend the k-edge-colouring to the edges of Q v in an AVD way and in such a way that the outputs of its G 1 are assigned a colour different from ψ(v) (to ensure properness -recall that AVDness is guaranteed due to degrees being different). From these arguments and previous ones, we deduce that the resulting k-edge-colouring of H is an AVD edge-colouring. Thus, H is of AVD class 1. Now, we claim that we have the desired equivalence between G and H.

• Assume H admits an NSD k-edge-colouring. Let us first analyse how an NSD k-edgecolouring φ behaves in Q. Once again, the G i 's must assign the same colour to all their outputs, and two of the G i 's cannot assign the same colour to their outputs, because of x. The important point here, is the role of the u i,j 's and v i,j 's. Recall that for every two distinct i, j ∈ {2, . . . , k}, an output of G 1 and an output of G i were connected, resulting in u i,j , which is adjacent to an end, v i,j , of some output of G j . From this, we deduce that the outputs of G 1 must be assigned colour k by φ. Indeed, if that was not the case, then there would be distinct i, j ∈ {2, . . . , k} such that either the outputs of G 1 are assigned colour 1 and the outputs of G i are assigned colour some α = 1, or the outputs of G 1 are assigned colour α and the outputs of G i are assigned colour 1, while the outputs of G j are assigned colour α + 1.

Then we would have σ(u i,j ) = α + φ(u i,j v i,j ) = σ(v i,j ), a contradiction to the fact that φ is an NSD k-edge-colouring of Q. So, the outputs of G 1 in Q must be assigned colour k.

Now consider an NSD k-edge-colouring φ of H. By the argumentation above, for every vertex v of G, in H the output of Q v connected to an output of G v must be assigned colour k. This means that every G v must have all its outputs assigned the same colour (by Theorem 2.5), which must be different from k. Also, due to how the G v 's were connected, if u and v are two adjacent vertices of G, then G u must assign by φ the same colour to all its outputs, that colour being different to the colour assigned to all the outputs of G v . From this, we deduce that if, for every v ∈ V (G), we set φ (v) = α, where α ∈ {1, . . . , k -1} is the colour assigned by φ to all outputs of G v in H, then φ must be a proper (k -1)-vertex-colouring of G.

• Assume now that G admits a proper (k -1)-vertex-colouring φ. We construct an NSD k-edge-colouring φ of H in the following way. For every G v , we consider, by φ , an NSD k-edge-colouring where all outputs are assigned colour φ(v). Note that, φ being a proper vertex-colouring, at this point φ must be proper. Also, due to the fifth item of Theorem 2.5, in every G v we can modify φ slightly, if needed, to avoid any sum conflict around vertices that result from output connections. Furthermore, since φ is a (k -1)-vertex-colouring, at this point no output is assigned colour k by φ . We now extend φ to the edges of the Q v 's. As remarked earlier, Q admits NSD k-edge-colourings, and, in every such colouring, the outputs of G 1 in Q must be assigned colour k. In H, we consequently extend φ to the edges of the Q v 's this way, with making sure that all outputs of the G 1 's are assigned colour k, while no sum conflict involves vertices resulting from the connection of Q v 's and G v 's (which can be guaranteed by the fifth item of Theorem 2.5). Eventually, this results in φ being an NSD k-edge-colouring of H. This shows that H is of NSD class 1.

Theorem 4.6. For every k ≥ 3, it is NP-hard to decide whether a given graph of AVD class 2 with maximum degree k is of NSD class 2.

Proof. Let k ≥ 3 be fixed. Quite similarly as for Theorems 4.3 and 4.4, the result can be proved by modifying the reduction in the proof of Theorem 4.5 slightly. Namely:

• Perform the reduction from the problem of deciding whether a given properly (k + 1)vertex-colourable graph G is properly k-vertex-colourable. This is an NP-hard problem by Lemma 4.2, since k ≥ 3.

• In Q, we here have k + 1 G i 's, G 1 , . . . , G k+1 , which are copies of G k,r .

• In Q, instead of connecting outputs of the G i 's through x, we connect them in pairs. Namely, for every two distinct i, j ∈ {1, . . . , k + 1}, we connect one output of G i and one output of G j to a vertex x i,j .

• The G v 's are copies of G k,r .

As earlier regarding Theorems 4.3 and 4.4, the modifications we made above to the construction of H guarantee, essentially, that the edge-colouring mechanisms described in the proof of Theorem 4.5 adapt the same way when considering k + 1 colours here. The maximum degree of H being k, and G k,r containing adjacent vertices with degree k, we have χ NSD (H) ≥ χ AVD (H) ≥ k + 1 by Theorem 2.5. From proper (k + 1)-vertex-colourings of G, we can deduce AVD (k + 1)-edgecolourings of H, which is thus of class 2. Because of the u i,j 's and v i,j 's, for the same reasons as previously, in every NSD (k + 1)-edge-colouring of Q the outputs of G 1 must be assigned colour k + 1. From this, similar arguments as in the proof of Theorem 4.5 apply here, and we can deduce an NSD (k + 1)-edge-colouring of H from a proper k-vertex-colouring of G, and vice versa.

Conclusion

In this work, our main goal was to further increase our general knowledge of the AVD and NSD chromatic indices, which led us to the following results:

• Through our results in Section 3, we have proved that deciding whether a graph is of AVD or NSD class 1 or 2 is NP-hard. As mentioned earlier, AVD and NSD edge-colourings being quite studied objects, it is surprising that these results have not been established already.

A remarkable fact is that we have proved these results for graphs with maximum degree k for every k ≥ 3: contrarily to what one could think, there is no k 0 such that graphs with maximum degree more than k 0 become easier to colour, due to the larger pool of colours.

To go a bit further, it would be interesting to wonder about restrictions of these results to graphs with particular structural properties. Notably, the gadgets M k we have introduced, which stand as our main tools throughout our NP-hardness reductions, do not comply well with planarity. Planar graphs being probably among the most investigated classes of graphs in the context of AVD and NSD edge-colourings, it would definitely be interesting to wonder about generalisations of our results to these graphs. Another quite investigated class of graphs is that of sparse graphs (i.e., with low density); again, it would be interesting to wonder about our results for this class of graphs. As a first step, note that, in our proof of Theorem 3.1, for the case k = 3 the reduced graph is actually obtained from a cubic graph by subdividing each edge exactly 3 times. Note that this actually makes the reduced graph bipartite. More interesting, is the fact that each edge of the cubic graph could actually be subdivided x times, for any x being a multiple of 3. This implies that the case k = 3 of Theorem 3.1 actually holds for bipartite subcubic graphs with arbitrarily large girth, thus being quite sparse. One possible direction for further research, could be to wonder about similar restrictions for our other results.

• Through our results in Section 4, we have proved that there exist infinitely many graphs for which the AVD and NSD chromatic indices are different. Again, a remarkable fact is that this holds for graphs with arbitrary maximum degree, which might sound surprising. Even stronger, we actually proved that graphs with AVD class 1 and NSD class 1, and similarly graphs with AVD class 2 and NSD class 2, are hard to recognise in general, unless P=NP.

Note that we actually proved this twice, as, regarding those concerns, Theorems 4.5 and 4.6 essentially accomplish the same things as Theorems 4.3 and 4.4. Nevertheless, we believe the slightly different edge-colouring mechanisms in all these NP-hardness proofs are interesting, in that they might be of some use towards going further with that line of research.

At this point, an appealing direction of research in those lines would concern the existence of graphs of AVD class 1 and NSD class 3. Despite many attempts, we were unsuccessful in designing even only one such graph. Towards this goal, one direction could be to wonder about the existence of graphs with similar colouring properties as our M k construction, plus additional properties such as being of AVD class 1. Another direction could be to consider small values of k first. Recall that, by Observation 4.1, every graph with maximum degree k = 3 of AVD class 1 is also of NSD class 1. For every k ≥ 4, recall that a graph with maximum degree k of AVD class 1 can be of NSD class 2, by Theorems 4.3 and 4.5. One first step could thus be to wonder about the existence of graphs with maximum degree 4 of AVD class 1 and NSD class 3.

Another question could be about the minimum order of graphs with differing AVD class and NSD class. Upper bounds on this minimum can be obtained e.g. from the arguments in the proofs we have provided in Section 4. For that, one can just consider any of the reduced graphs H constructed in one of the four main proofs, with making the extra assumption that G is empty. Due to our arguments, graphs of this sort can be constructed for any maximum degree k ≥ 3, and they are of different AVD class and NSD class due to the arguments we have provided. It can be noted, however, that they are rather large.

Figure 1 :

 1 Figure1: The gadgets M 3 and G 4,4 from Section 2. In (a), wiggly edges are outputs. In (b), wiggly edges are outputs of the four copies of M 4 in G 4,4 , those surrounded by bold lines being the four outputs of G 4,4 . In (b), the white vertices are the four support vertices of G 4,4 . In each case, is also given an AVD edge-colouring using the least number of colours possible (4 in (a), 5 in (b)). In (a), the set of incident colours is given for every vertex of maximum degree[START_REF] Hocquard | On various problems related to edge-colorings[END_REF]. Note also that, in (b), the edges of the four copies of M 4 are not coloured the same way, to illustrate the fact that, in an AVD 5-edge-colouring of G 4,4 , even though we have some control over the sets of incident colours achieved for the support vertices, we have less control on how those sets are obtained.

  v

Figure 2 :

 2 Figure 2: Illustration of the connection and attachment operations.

Figure 3 :

 3 Figure 3: Illustration of the reduction in the proof of Theorem 3.3. (a) depicts part of a graph G and of a proper vertex-colouring. (b) depicts part of the reduced graph H and of a corresponding AVD edge-colouring. In (b), wiggly edges of H are outputs of the G v 's.

Observation 4 . 1 .

 41 If G is a graph of AVD class 1 with maximum degree 3, then G is of NSD class 1.

3

 3 and the edges incident to v are e 1 , e 2 , e 3 , then, because φ is proper, we must have {φ(e 1 ), φ(e 2 ), φ(e 3 )} = {1, 2, 3}, and thus σ(v) = 6;• if d(v) =2 and the edges incident to v are e 1 , e 2 , then we must have {φ(e 1 ), φ(e 2 )} = {1, 2}, {φ(e 1 ), φ(e 2 )} = {1, 3}, or {φ(e 1 ), φ(e 2 )} = {2, 3}, and thus σ(v) = 3, σ(v) = 4, or σ(v) = 5, respectively; • if d(v) = 1 and the edge incident to v is e 1 , then we must have {φ(e 1 )} = {1}, {φ(e 1 )} = {2}, or {φ(e 1 )} = {3}, and thus σ(v) = 1, σ(v) = 2, or σ(v) = 3, respectively.

Figure 4 :

 4 Figure 4: Part of the reduction in the proof of Theorem 4.3, in the special case where k = 4.Wiggly edges are outputs of some G k,r . Due to space limitation, note that not all pairs {u i,j, , v i,j, } are represented.

Figure 5 :

 5 Figure 5: Part of the reduction in the proof of Theorem 4.5, in the special case where k = 4.Wiggly edges are outputs of some G k,r . Due to space limitation, note that, in (a), not all pairs {u i,j , v i,j } are represented.

  [START_REF] Hocquard | On various problems related to edge-colorings[END_REF]. In particular, here H is of NSD class 3 (which can be proved quite similarly as in the proof of Theorem 4.3), and it is of AVD class 2 if and only if G is properly k-vertex-colourable.4.2. Determining χ NSD when χ AVD is fixedAgain, the next result cannot be extended to the case where k = 3, by Observation 4.1. For every k ≥ 4, it is NP-hard to decide whether a given graph of AVD class 1 with maximum degree k is of NSD class 1.Proof. Let k ≥ 4 be fixed. We prove the result by reduction from the problem of deciding whether a properly k-vertex-colourable graph is properly (k -1)-vertex-colourable (which is NP-hard by Lemma 4.2). That is, given a properly k-vertex-colourable graph G, we construct, in polynomial time, a graph H of AVD class 1 with maximum degree k such that G is properly (k -1)-vertexcolourable if and only if H is of NSD class 1.

	Theorem 4.5.

All decision problems considered here being obviously in NP, their NP-hardness implies their NP-completeness.

Graphs with maximum degree 2 are paths and cycles, for which the AVD and NSD chromatic indices are easy to determine; investigating hardness results thus makes sense only for graphs with maximum degree at least

[START_REF] Hocquard | On various problems related to edge-colorings[END_REF] Throughout this work, unless specified otherwise, we deal with the elements of any graph introduced through a figure following the terminology given in that very figure. In contexts where multiple copies of one such graph are present, we will, however, have to tweak this terminology a bit to avoid any ambiguity. In such situations, elements will be renamed in an explicit way.

Note that there is no constraint on ∆(G) in Lemma 4.2, which might, in particular, verify ∆(G) > k.