Frédéric Havet
email: fhavet@sophia.inria.fr

Stéphan Thomassé
email: thomasse@lirmm.fr

Complexity of (p, 1)-total labelling

Keywords: Total labelling, total colouring, distance constrained colouring. 1991 MSC: 05C15, 68R10

. In this paper we assume p ≥ 2. It is easy to show that λ p (G) ≥ ∆ + p -1, where ∆ is the maximum degree of G. Moreover, when G is bipartite, ∆ + p is an upper bound for λ p (G), leaving only two possible values. In this paper, we completely settle the computational complexity of deciding whether λ p (G) is equal to ∆ + p -1 or to ∆ + p when G is bipartite. This is trivial when ∆ ≤ p, polynomial when ∆ = 3 and p = 2, and NP-complete in the remaining cases.

Introduction

The Frequency Assignment Problem asks for assigning frequencies to transmitters in a broadcasting network with the aim of avoiding undesired interference. One of the graph theoretical models of this problem which is well elaborated is the notion of distance constrained labelling of graphs. An L(p, q)-labelling of a graph G is a mapping from the vertex set of G into nonnegative integers such that the labels assigned to adjacent vertices differ by at least p, and labels assigned to vertices of distance 2 differ by at least q. The span of such a labelling is the maximum label used. This model was introduced by Roberts [START_REF] Roberts | Private communication to J. Griggs[END_REF] and since then the concept has been intensively studied (See the survey of Yeh [START_REF] Yeh | A survey on labeling graphs with a condition at distance two[END_REF]).

In [START_REF] Havet | 1)-total labelling of graphs[END_REF], Havet and Yu introduced the notion of (p, 1)-total labelling of a graph which corresponds to an L(p, 1)-labelling of its first subdivision of a graph G. The first subdivision (also called incidence graph) of a graph G is the graph s 1 (G) obtained from G by inserting one vertex along each edge of G. Let G = (V, E) be a graph and p be a positive integer. A (p, 1)-total labelling of G is a mapping L from V ∪ E into {0, . . . , l}, for some integer l, such that:

• if x and y are adjacent vertices then L(x) = L(y);

• if e and f are adjacent edges then L(e) = L(f );

• if an edge e is incident to a vertex x then |L(x) -L(e)| ≥ p.

A (1, 1)-total labelling coincides with the usual notion of total colouring. Clearly, every graph admits a (p, 1)-total labelling, if l is chosen large enough. The minimum l for which G has a (p, 1)-total labelling into {0, . . . , l} is denoted by λ p (G) and referred as (p, 1)-total labelling number. In [START_REF] Havet | 1)-total labelling of graphs[END_REF] Havet and Yu established the following easy bounds (here χ stands for the chromatic number, χ ′ the chromatic index and ∆ for the maximum degree):

Proposition 1 (Havet and Yu, [START_REF] Havet | 1)-total labelling of graphs[END_REF]) Let G = (V, E) be a graph with at least one edge. Proposition 2 (Havet and Yu, [START_REF] Havet | 1)-total labelling of graphs[END_REF]) Let G = (V, E) be a graph with at least one edge.

(i) λ p (G) ≤ χ(G) + χ ′ (G) + p -2. (ii) λ p (G) ≤ 2∆(G) + p -1.
In this paper, we are interested in the complexity of computing λ p (G). In the more general case of L(p, 1)-labellings, Griggs and Yeh [START_REF] Griggs | Labelling graphs with a condition at distance 2[END_REF] proved that determining the minimum span of an L(2, 1)-labelling of a graph G is an NPhard problem. Later Fiala et al. [START_REF] Fiala | Fixed-parameter complexity of λlabelings[END_REF] proved that deciding if this span is at most k is NP-complete for every fixed k ≥ 4.

In the case of total colouring (or (1, 1)-total labelling), Sánchez-Arroyo [START_REF] Sánchez-Arroyo | Determining the total colouring number is NP-hard[END_REF] first proved that it is NP-hard to determine the total chromatic number of graphs. Furthermore, McDiarmid and Sánchez-Arroyo [START_REF] Mcdiarmid | Total colouring regular bipartite graphs is NP-hard[END_REF] showed that it is still NP-hard when restricted to k-regular bipartite graphs (if k ≥ 3). Here we study the problem when p ≥ 2. Contrary to total colouring, determining the (p, 1)-total labelling number of a regular bipartite graph is easy since it is always ∆(G) + p by Propositions 1 and 2 (since χ(G) = 2 and χ ′ (G) = ∆(G) by König's theorem). Hence, we will study the problem restricted to the class of bipartite graphs. If G is bipartite, Propositions 1 and 2 yield λ p (G) ∈ {∆(G) + p -1, ∆(G) + p}. Hence we investigate the complexity of the following problem: ∆-Bipartite (p, 1)-Total Labelling Problem: INSTANCE: Bipartite graph G with maximum degree ∆. QUESTION: Does λ p (G) = ∆ + p -1?

Note that Proposition 1 (iii) implies that this problem is trivial when ∆ ≤ p since it is always answered in the negative.

The aim of this paper is to prove the NP-completeness of the ∆-Bipartite (p, 1)-Total Labelling Problem for any ∆ ≥ p+1 except for ∆ = 3 and p = 2 in which case we give a polynomial-time algorithm to solve it. In Section 3 we first give a polynomial-time algorithm that decides if λ 2 (G) = 4 or λ 2 (G) = 5 for a bipartite graph with maximum degree 3. This algorithm is based on induced matching in bipartite graphs. We also show that the same decision problem for graphs (not necessarily bipartite) with maximum degree 3 is NP-complete. In Section 4, we prove the NP-completeness of the ∆-Bipartite (p, 1)-Total Labelling Problem in all other cases. To achieve it, we need to distinguish three cases: ∆ ≥ 2p (Section 4.1), 2p -1 ≥ ∆ ≥ p + 2 (Section 4.2) and ∆ = p + 1 (Section 4.3). Note that these results imply that determining the minimum span of an L(p, 1)-labelling of a bipartite graph is NP -hard. For trees determining the minimum span of an L(2, 1)-labelling is nontrivial but a polynomial time algorithm based on bipartite matching was presented in [START_REF] Chang | The L(2, 1)-labeling problem on graphs[END_REF].

Preliminaries

Let G = (V, E) be a graph. The degree of a vertex v is denoted by d G (v) or simply d(v), when G is clear from the context. A path is a non-empty graph P of the form

V (P ) = {v 0 , v 1 , . . . , v k } E = {v 0 v 1 , v 1 v 2 , . . . , v k-1 v k },
where the v i are all distinct. The vertices v 0 and v k are called the ends of P . We often refer to a path by the natural sequence of its vertices, writing

P = v 0 v 1 . . . v k .
For any pair of vertices x and y, an xy-path is a path with ends x and y.

Given two sets of vertices X and Y of G, the distance from X to Y denoted dist(X, Y ) is the length of a shortest xy-path with x ∈ X and y ∈ Y . The distance between two edges uv and xy is defined by dist(uv, xy) = dist({u, v}, {x, y}).

We will often make use of the following (simple) facts:

(v) = k -1, then L(v) ∈ {0, 1, k + p -2, k + p -1}.
Proof:

(i) Suppose that L(v) / ∈ {0, k + p -1}. Then |{L(v) -p + 1, . . . , L(v) + p - 1} ∩ {0, . . . , k + p -1}| ≥ p + 1. Hence at most k -1 labels are available to colour the edges adjacent to v. So d(v) ≤ k -1. (ii) It follows directly from (i). (iii) Suppose that L(v) / ∈ {0,
(x) = L(y) = L(z). (vi) If p ≥ 3 the graph I in Fig. 1 is a subgraph of G with d G (a) = d G (b) = d G (c) = d G (d) = p + 1 and d G (f 1 ) = d G (f 2 ) = p, then L(a) = L(c) and L(b) = L(d).
Proof:

(i) Trivial.

(ii) Assume for contradiction that there are two edges xy and uv, both labelled p, at distance one (distance zero is impossible by definition of (p, 1)-total labelling).Without loss of generality, we may assume that yu is an edge. Then y is labelled 0 and u is labelled 2p or y is labelled 2p and u is labelled 0. Thus the unique label allowed by its ends for the edge yu is p, which is a contradiction. (iii) By Proposition 3 (i), L(x) = 0 and L(y) = 2p. Moreover the edge xu is labelled in {p, . . . , 2p}, so L(u) ≤ p and the edge uy is labelled in {0, . . . , p}, thus L(u) ≥ p. Hence L(u) = p, so L(xu) = 2p and L(uy) = 0. (iv) It follows directly from (iii). (v) It follows also easily from (iii). (vi) Suppose for a contradiction that it is not true. By Proposition 3 (ii), the edges ab and cd are both labelled p and L(a) = L(d) and L(b) = L(c).

Without loss of generality, we may assume that L(b) = 0 and L(d) = 2p. The vertex f 1 of I has degree p so by Proposition 3 (iii), L(f

1 ) ∈ {0, 1, 2p-1, 2p}. Moreover L(d) = 2p and L(f 1 d) ≤ p -1, so L(f 1 ) = 2p -1.
Hence L(e 1 f 1 ) ≤ p -1 so L(e 1 ) ≥ p. Now L(be 1 ) ≥ p, so L(e 1 ) ≤ p. Thus L(e 1 ) = p and L(be 1 ) = 2p. Analogously L(be 2 ) = 2p which is a contradiction. Let G be a bipartite graph with maximum degree three. Our aim is to show a polynomial-time algorithm which decides if λ 2 (G) is equal to 4 or 5.

An induced matching is a matching M of G such that any two distinct edges of M are at distance at least two. A good matching is an induced matching M such that every vertex of maximum degree is incident to an edge of M. Observe that from the definition of a good matching, an edge which is incident to two vertices of maximum degree is necessarily in every good matching. Conversely, an edge which is at distance one from a maximum degree vertex is never in a good matching. Because every vertex of degree 3 is incident to an edge of M, the graph G \ M has maximum degree 2. So it is the union of disjoint (even) cycles and paths. Let D be an orientation of G \ M such that every cycle is a directed cycle and every path is a directed path (i.e. an orientation such that |d + (x)d -(x)| ≤ 1 for every vertex x). If a cycle or a path of G \ M is not incident to any edge of M (and thus forms a connected component of G), we simply label its vertices by an alternating 0,1 sequence and its edges by an alternating 3,4 sequence. So we assume now that every component of G \ M contains a vertex of V (M). Let P be the set of maximal oriented paths of D whose internal vertices are not incident to an edge of M (such a path can have the same endvertices when it comes from a cycle of D which is incident to exactly one edge of M).

Observe that every arc of D belongs to a unique path of P.

We label the vertices and the arcs of each path P = (x 0 , x 1 , . . . , x l ) of P as follows:

• Suppose that x 0 and x l are both incident to an edge of M. Then since M is a good matching, we have l ≥ 2.

• If l is even, then L(x 0 ) = L(x l ).

If L(x 0 ) = 0 then for 0 ≤ i ≤ l -1, if i is even, set L(x i ) = 0 and L(x i x i+1 ) = 3, and, if i is odd, set L(x i ) = 1 and L(x i x i+1 ) = 4.

If L(x 0 ) = 4 then for 0 ≤ i ≤ l -1, if i is even, set L(x i ) = 4 and L(x i x i+1 ) = 1, and, if i is odd, set L(x i ) = 3 and L(x i x i+1 ) = 0.

• If l is odd, then L(x 0 ) = L(x l ). If L(x 0 ) = 0 then set L(x 0 x 1 ) = 3, L(x 1 ) = 1, L(x 1 x 2 ) = 4, L(x 2 ) = 2 and L(x 2 x 3 ) = 0. Furthermore, for 3 ≤ i ≤ l -1, if i is odd, set L(x i ) = 4 and L(x i x i+1 ) = 1, and if i is even, set L(x i ) = 3 and L(x i x i+1 ) = 0. If L(x 0 ) = 4 then set L(x 0 x 1 ) = 1, L(x 1 ) = 3, L(x 1 x 2 ) = 0, L(x 2 ) = 2 and L(x 2 x 3 ) = 4. Moreover, for 3 ≤ i ≤ l -1, if i is odd, set L(x i ) = 0 and L(x i x i+1 ) = 3, and, if i is even, set L(x i ) = 1 and L(x i x i+1 ) = 4.
• If x 0 is incident to an edge of M, and x l is not, we suppose without loss of generality that L(x 0 ) = 0. We colour L(x i ) = 0 and L(x

i x i+1 ) = 3, if i is even, and L(x i ) = 1 and L(x i x i+1 ) = 4 if i is odd.
The case x l incident to an edge of M is treated similarly.

To see that L is a (2, 1)-total labelling of G, observe that a vertex x ∈ V (M) is the origin of at most one directed path P of P and the end of at most one directed path Q of P. Now the first edge of P is coloured 3 (resp. 1) and the last edge of Q is coloured 4 (resp. 0) if L(x) = 0 (resp. 4). Thus the edges incident to x get different integers at distance at least two from L(x). 2

A restricted good matching is a good matching such that each edge is incident to a vertex of maximal degree. Clearly, a graph has a good matching if and only if it has a restricted good matching. From now on, by good matching, we understand restricted good matching.

Theorem 2

The following problem is solvable in polynomial time: INSTANCE: Graph G with maximum degree 3.

QUESTION: Does G have a good matching?

Proof: Given a graph G with maximum degree 3, the following algorithm finds a good matching of G if one exists or answers "G has no good matching" otherwise.

For any edge e, we denote by B 2 (e) the union of the set of edges and vertices at distance strictly less than two from e. If F is a set of edges, then

B 2 (F ) = e∈F B 2 (e). Note that if e is an edge of a good matching M then B 2 (e) ∩ M = {e}.
During the execution of the algorithm, M is the set of edges that are selected to be in the desired good matching and S denotes the set of vertices that must be incident to an edge of a good matching and that are not yet incident to an edge of M. Finally, H is the subgraph of G where the remaining edges of the good matching can be.

Good Matching(G)

Step 0: Initially, let H be G, S be the set of vertices of degree 3 and M be the set of edges with both endvertices in S.

Step 1: If M is an induced matching (in particular if M = ∅), then remove B 2 (M) from H and the endvertices of each edge of M from S. Otherwise return "G has no good matching".

Step 2: Remove the edges of every path of length 2 joining two vertices of S.

Step 3: Repeat until no vertex u of S satisfies one of the following cases:

Case 1: If u has degree 0 in H then return "G has no good matching". Case 2: If u has a unique neighbour v or a neighbour v that has degree one in H, then add uv to M, remove B 2 (uv) from H and u from S.

Case 3: If there is a path uvw in H such that w is not adjacent to any vertex of S then add uv to M, remove B 2 (uv) from H and u from S.

Step 4: Repeat until S = ∅:

Pick a vertex u of S with minimum degree in H. Take a path uvwx starting at u (observe that x ∈ S). Add uv to M, remove uvw from H and remove u from S.

Step 5: Return M.

At

Step 0, S is initialized to the set of vertices of degree 3.

By Proposition 3 (ii), any good matching must contain the edges joining two vertices of degree 3. So M is initialized to this set. At Step 1, we check that M is an induced matching which is a necessary condition for G to have a good matching.

From

Step 2, M is an induced matching. Indeed each time, we will add an edge e to M, we remove B 2 (e) from the graph G. Hence, all the edges of the remaining graph are at distance at least 2 from e in particular those edges that will be added to M after e. Therefore once S will be reduced to the emptyset, M will be a good matching.

At

Step 2, we remove all the paths of length 2 between vertices of S since their edges are in no good matching.

Let us prove that at each iteration of the loop of Step 3, the following "correctness statement" holds : if there is a good matching M 1 then there is a good matching M 2 containing M. Case 1: There is no more edges to be incident to u. Thus G has no good matching containing M, so by the correctness statement G has no good matching.

Case 2: Suppose that there is a good matching M 1 containing M. Let e u be the edge incident of M 1 to u. Let us prove that M 2 = (M 1e u ) ∪ {uv} is also a good matching. Let e be an edge of M 2 \ {uv} that is the closest to uv and let P be a smallest path connecting e to uv in (the initial) G. If v is an endvertex of P , then the two first edges of P are not in H and thus not in M.

If not dist(e u , e) ≤ dist(uv, e). In both cases, dist(uv, e) ≥ 2. Thus M 2 is an induced matching and then a good matching. Analogously one can prove the correctness statement if we are in Case 3.

At the end of Step 3, H has a nice structure: a path joining to vertices of S with no internal vertices in S has length exactly 3, and each vertex of S is adjacent to at least one such path. In particular this implies that G has a good matching. Then Step 4 extends the matching M in a good matching. 2 Theorems 1 and 2 immediatly imply:

Corollary 1 The 3-Bipartite (2, 1)-Total Labelling Problem is solvable in polynomila time. Let C = {C 1 , . . . , C n } be a collection of clauses over a set U of variables. We will construct a graph G(C, U). For every variable u ∈ U, create a variable subgraph P u defined as follows:

NP-completeness for general graphs

V (P u ) = n i=1 {a i (u), b i (u), s i (u)} E(P u ) = n i=1 {a i (u)b i (u), a i (u)s i (u), a i s i-1 (u)} with s 0 (u) = s n (u).
For every clause C i = x ∨ y ∨ z, create a subgraph D i defined as follows:

V (D i ) = {a i (x), b i (x), a i (y), b i (y), a i (z), b i (z), c i , d i , t i (x), t i (y), t 1 i (z), t 2 i (z)} . . . a1(u) s1(u) an(u) b1(u) bn(u) b2(u) a2(u) s2(u) bn-1(u) an-1(u) sn-1(u) s0(u) Fig. 2. The variable subgraph P u E(D i ) = {a i (x)b i (x), b i (x)t i (x), a i (y)b i (y), b i (y)t i (y), a i (z)b i (z), b i (z)t 1 i (z), b i (z)t 2 i (z), c i d i , c i t i (x), c i t i (y), d i t 1 i (z), d i t 2 i (z)} a i (z) b i (z) t 1 i (z) t 2 i (z) c i d i b i (x) a i (y) b i (y) t i (y) t i (x) a i (x) Fig. 3. The clause subgraph D i
If x is a non-negated literal u identify the vertices a i (u) and b i (u) of P u with the vertices a i (x) and b i (x) of D i . We also add a new vertex b ′ i (u) of degree one adjacent to b i (u) so that this vertex has degree 3 in G(C, U).

If x is a negated literal ū create two new vertices q i (u) and r i (u) and join them both to the vertices b i (u) of P u and a i (x) of D i .

Let us prove now that G(C, U) has a (2, 1)-total labelling in {0, . . . , 4} if and only if there is a truth assignment such that each clause in C has at least one true literal and at least one false literal. Suppose first that there exists a (2, 1)-total labelling L of G(C, U) in {0, . . . , 4}.

A = {a i (u), b i (u) | 1 ≤ i ≤ n, u ∈ U}∪{a i (x), b i (x), a i (y), b i (y), a i (z), b i (z), c i , d i | C i = x ∨ y ∨ z clause} is the set of vertices of degree 3 in G(C, U)
. By construction, every vertex of A has exactly one neighbour in A. Hence by Proposition 3 (i), every vertex of A is labelled 0 or 4 and an edge with its two ends in A is labelled 2.

Let us show that for every u ∈ U, all the a i (u) are labelled the same (0 or 4). By Proposition 3 (i), for all 1 ≤ i ≤ n, the a i (u) are labelled 0 or 4 and L(a i (u)b i (u)) = 2. Suppose they are not all labelled the same. Then there exists i 0 < i 1 such that L(a i 0 (u)) = 0 = L(a i 1 +1 (u)) and L(a i (u)) = 4 if i 0 < i ≤ i 1 . Then by Proposition 4 (i), L(a i 0 (u)s i 0 (u)) = 4, L(s i 0 (u)) = 2 and L(s i 0 (u)a i 0 +1 (u)) = 0, then L(a i 0 +1 (u)s i 0 +1 (u)) is necessary 1. So L(s i 0 +1 (u)) = 3 and L(s i 0 +1 (u)a i 0 +2 (u)) = 0. And so on by induction, if i 0

< i ≤ i 1 , L(s i-1 (u)a i (u)) = 0, L(a i (u)s i (u)) = 1. But by Proposition 3 (i), L(a i 1 (u)s i 1 (u)) = 0 which is a contradiction.
Hence we may define the truth assignment φ by φ(u) = true if L(a i (u)) = 2p and φ(u) = f alse if L(a i (u)) = 0. Let us prove that each clause in C has at least one true literal and at least one false literal under φ.

Let C i = x ∨ y ∨ z be a clause. Let t be one of its literals. If t is a non-negated literal u, then L(a i (t)) = L(a i (u)) since a i (t) = a i (u). If t is a negated literal ū then, according to Proposition 4 (iv), L(a i (t)) = L(b i (u)) = L(a i (u)
) since a i (x) and b i (u) have two common neighbours q i (u) and r i (u). Hence to prove the result it suffices to prove that L(a i (x)), L(a i (y)) and L(a i (z)) are not all equal.

Suppose (reductio ad absurdum) that they are all equal. Without loss of generality, we may suppose they are 0. Then since a i (x)b i (x), a i (y)b i (y) and a i (z)b i (z) are edges labelled 2, then b i (x), b i (y) and b i (z) are labelled 4. Now c i d i is also labelled 2 and, because b i (z) and d i have two common neighbours, they are labelled the same by Proposition 4 (iv). Thus d i is labelled 4 and so c i is labelled 0. Now c i and b i (x) have a common neighbour t i (x) so L(t i (x)c i ) = 4 according to Proposition 4 (iii). Analogously, L(t i (y)c i ) = 4 which is a contradiction.

Let us now suppose that there is a truth assignment φ such that each clause in C has at least one true literal and at least one false literal. For every variable u ∈ U, we do the following

-if φ(u) = true then, for 1 ≤ i ≤ n, set L(a i (u)) = 4, L(b i (u)) = 0, L(a i (u)b i (u)) = 2
, and label the neighbours of a i (u) different from b i (u) with 3. We then label a i (u)s i (u) with 0 and a i (u

)s i-1 (u) with 1. -if φ(u) = f alse then, for 1 ≤ i ≤ n, set L(a i (u)) = 0, L(b i (u)) = 4, L(a i (u)b i (u)) = 2,L(s i (u)) = 1, L(a i (u)s i (u)) = 3 and L(a i (u)s i-1 (u)) = 4.
For every literal

x of clause C i , set L(a i (x)) = 4, L(b i (x)) = 0, L(a i (x)b i (x)) = 2 if φ(x) = true and set L(a i (x)) = 0, L(b i (x)) = 4, L(a i (x)b i (x)) = 2 if φ(x) = f alse. Note that if x is a non-negated literal u then the vertices a i (x) = a i (u), b i (x) = b i (u)
and the edge a i (x)b i (x) = a i (u)b i (u) get the same label with the labelling of the clause and the labelling of the variable.

If x is the negated literal ū, then a i (x) and b i (u) are labelled the same. Hence set

L(q i (u)) = L(r i (u)) = 1, L(b i (u)q i (u)) = L(r i (u)a i (x)) = 3 and L(b i (u)r i (u)) = L(q i (u)a i (x)) = 4 if they are labelled 0 and L(q i (u)) = L(r i (u)) = 3, L(b i (u)q i (u)) = L(r i (u)a i (x)) = 1 and L(b i (u)r i (u)) = L(q i (u)a i (x)) = 0 if they are labelled 4.
Let us now extend the labelling to each clause graph D i . Since C i has one true literal and one false literal, then {b i (x), b i (y), b i (z)} has one vertex labelled 0 and one is labelled 4.

-If L(b i (x)) = L(b i (y)) = 0 and L(b i (z)) = 4, set L(c i ) = 0, L(d i ) = 4, L(c i d i ) = 2, L(t i (x)) = L(t i (y)) = 1 and L(t 1 i (z)) = L(t 2 i (z)) = 3. -If L(b i (x)) = L(b i (z)) = 0 and L(b i (y)) = 4, set L(c i ) = 4, L(d i ) = 0, L(c i d i ) = 2, L(t i (x)) = 2 and (t i (y)) = 3, L(t 1 i (z)) = L(t 2 i (z)) = 1, L(ct i (x) = 0, L(t i (x)b i (x)) = 4.
In other cases, we proceed analogously, since x and y are equivalent and by symmetry of the labelling l → 2pl. . . .

∆-p 2

B n (u)

B 1 (u) B 2 (u) p p p ∆-p 2 B 0 (u) A n (u) A 1 (u) A 2 (u) ∆-p 2
Fig. 4. The variable subgraph P (u)

Let C i be a clause and u ∈ U a variable. Let s i (u) be a vertex in A i (u). This vertex will correspond to the non-negated literal u in the clause C i . Let us create a negation subgraph N i (u) containing a vertex s i (ū) corresponding to the negated literal ū in the clause For each clause C i create a vertex v i . Connect v i to s i (l) for every literal l in C i .

C i . The vertex set V (N i (u)) is A i (u) ∪ {p i (u), q i (u), s i (ū)} ∪ R i (u), with R i (u) a set of ∆ -p new vertices and E(N i (u)) = {ap i (u) | a ∈ A i (u)} ∪ {rq i (u) | r ∈ R i (u)} ∪ {rs i (ū) | r ∈ R i (u)} ∪ {p i (u)q i (u)} (see Fig. 5). p ∆ -p p i (u) s i (ū) R i (u) A i (u) q i (u)
Finally, add as many as necessary extra vertices of degree 1 adjacent to the vertices of S = u∈U V (P (u)) ∪ u∈U,1≤i≤n [V (N i (u) \ {p i (u)}] in such a way that all these vertices get degree ∆.

By construction, G(C, U) is bipartite with maximum degree ∆. Let us prove that λ p (G(C, U)) = ∆ + p -1 if and only if there is a truth assignment such that each clause in C has at least one true literal and at least one false literal.

If there is a truth assignment φ, we do the following for each variable u:

-Label the edges of P (u) with labels of {p, . . . , ∆ -1}. This is possible by König's theorem since P (u) is bipartite of maximal degree ∆p.

-If φ(u) = true then label each a ∈ A i (u) with ∆ + p -1 and each b ∈ B i (u) with 0. Otherwise label each a ∈ A i (u) with 0 and each b ∈ B i (u) with ∆ + p -1. -Label the edges of {rq i (u) | r ∈ R i (u)} ∪ {rs i (ū) | r ∈ R i (u)} with labels of {p, . . . , ∆ -1}. -If φ(u) = true then label each r ∈ R i (u) with ∆ + p -1, and q i (u) and s i (ū) with 0. Otherwise label each r ∈ R i (u) with 0, and q i (u) and s i (ū) with ∆ + p -1. -If φ(u) = true then label the edges of {ap i (u) | a ∈ A i (u)} with {0, . . . , p -1}, p i (u)q i (u) with ∆ + p -1 and p i (u) with 2p -1. Otherwise label the edges of {ap i (u) | a ∈ A i (u)} with {∆, . . . , ∆ + p -1}, p i (u)q i (u) with 0 and p i (u) with ∆p. This is valid since ∆ ≥ 2p.

Now each vertex v i is adjacent to the p + 1 vertices s i (l) for l literal of C i . These vertices are labelled in {0, ∆ + p -1} with at least one labelled 0 and at least one labelled ∆ + p -1. Let us denote by t 1 , t 2 , . . . , t j the neighbours of v i labelled 0 and t j+1 , . . . , t p+1 the neighbours of v i labelled ∆ + p -1. For 1 ≤ l ≤ j, label v i t j with ∆ + pl and for j + 1 ≤ l ≤ p + 1, label v i t j with lj + 1. Now label v i with 2pj. This is possible because ∆ ≥ 2p.

This labelling may trivially be extended to the extra vertices and their incident edges to get a (p, 1)-total labelling of G(C, U).

Suppose now that there is a (p, 1)-total labelling L of G(C, U) in {0, . . . , ∆ + p -1}. By Proposition 3 (i), for any u ∈ U, all the vertices in n i=1 A i (u) have the same label L u ∈ {0, ∆ + p -1} and all the vertices in n i=0 B i (u) are labelled with the integer Lu of {0, ∆ + p -1} \ L u . Moreover the edges of P (u) are labelled in {p, . . . , ∆ -1} by Proposition 3 (ii). Now, since every vertex a of a i (u) has degree ∆p in P (u), each label of {p, . . . , ∆ -1} is assigned to an edge incident to a in P (u).

Let us show that L(s i (ū)) = Lu . Without loss of generality, we may assume that L u = ∆ + p -1.

Suppose for a contradiction that L(s i (ū)) = 0. By Proposition 3 (i), L(s i (ū)) = ∆+ p -1. Furthermore by Proposition 3 (ii), each vertex in R i (u) is labelled 0, L(q i (u)) = ∆+ p -1, and the ∆-p edges of {q i (u)r i (u)} ∪{q i (u)r | r ∈ R i (u)} are labelled with the ∆p integers of {p, . . . , ∆ -1}. Hence the p + 1 edges adjacent to p i (u) are labelled in {0, . . . , p -1}. This is a contradiction.

Let φ be the truth assignment defined by φ

(u) = true if L u = ∆ + p -1 and φ(u) = f alse if L u = 0.
Let us prove that each clause in C has at least one true literal and at least one false literal. The vertex v i is adjacent to p + 1 vertices, namely the s i (l) for all the literal l of C i . If C i has all its literals true (resp. false) then all the neighbours of v i are labelled 0 (resp. ∆ + p -1). Moreover they are incident to edges labelled p, . . . , ∆-1 in P (u) or N i (u). Hence the p+1 edges incident to v i cannot be labelled since they are only p labels available, those of {0, . . . , p -1} (resp. {∆, . . . , ∆ + p -1}). if i is even. The vertex s i (u) will correspond to the non-negated literal u in C i .

. . .

∆-p 2 ∆-p 2 ∆-p 2 B 0 (u) B n (u) B 1 (u) B 2 (u) s 1 (u) s 2 (u) s n (u)
Fig. 6. The variable subgraph P (u)

Let us now create a negation subgraph N i (u) containing a vertex s i (ū) corresponding to the negated literal ū in the clause

C i . The vertex set V (N i (u)) is {s i (u), p 1 i (u), p 2 i (u), r i (u), s i (ū)} ∪ Q i (u) ∪ T i (u) ∪ V i (u)
where Q i (u) is a set of p-1 vertices and T i (u) and V i (u) are two sets of ∆-p-1 vertices. The edge set

E(N i (u)) is {s i (u)p 1 i (u), s i (u)p 2 i (u), r i (u)s i (ū)} ∪ {pq | p ∈ {p 1 i (u), p 2 i (u)}, q ∈ Q i (u)} ∪ {xr i (u), | x ∈ Q i (u) ∪ T i (u)} ∪ {vs i (ū) | v ∈ V i (u)}. Now for each clause C i = x ∨ y ∨ z create a clause subgraph C(i) that con- nects the three vertices s i (x), s i (y) and s i (z). The vertex set V (C(i)) is {s i (x), s i (y), s i (z), p 1 i , p 2 i , r i , w i } ∪D 1 i ∪D 2 i ∪Q i ∪T i with D 1 i , D 2 i , Q i and T i four sets of cardinality respectively ∆-p 2 , ∆-p 2 , p -1 and ∆ -p -1. The edge set E(C(i)) is {s i (z)p 1 i , s i (z)p 2 i , r i w i } ∪ {pq | p ∈ {p 1 i , p 2 i }, q ∈ Q i } ∪ {xr i , x ∈ Q i ∪ T i } ∪ {w i d | d ∈ D 1 i ∪ D 2 i } ∪ {s i (x)d | d ∈ D 1 i } ∪ {s i (y)d | d ∈ D 2 i }. ∆ -p -1 ∆ -p -1 r i (u) p 1 i (u) p 2 i (u) p -1 s i (ū) s i (u) Q i (u) V i (u) T i (u)
Fig. 7. The negation subgraph N i (u)

∆ -p -1 p -1 p 2 i p 1 i T i s i (z) Q i D 1 i w i r i ∆-p 2 ∆-p 2 s i (y) s i (x) D 2 i Fig. 8. The clause subgraph C(i)
Finally, add as many as necessary extra vertices of degree 1 adjacent to the vertices of

S = u∈U V (P (u))∪ 1≤i≤n [{r i , w i }∪T i ]∪ u∈U,1≤i≤n [{r i (u), s i (ū)}∪ T i (u) ∪ V i (u)] and S ′ = u∈U,1≤i≤n Q i (u) ∪ 1≤i≤n Q i ∪ D 1 i ∪ D 2
i in such a way that the vertices of S get degree ∆ and those of S ′ degree ∆ -1.

By construction, G(C, U) is bipartite with maximum degree ∆. Let us prove that λ T p (G(C, U)) = ∆ + p -1 if and only if there is a truth assignment such that each clause in C has at least one true literal and at least one false literal. Suppose first that there exists such a truth assignment φ. Let us exhibit a (p, 1)-total labelling L of G(C, U) in {0, . . . , ∆ + p -1}. Let u be a variable.

Suppose that φ(u) = true. Then label the vertices and edges of P (u) as follows:

-Label the edges of P (u) with labels of {p, . . . , ∆ -1}. This is possible by König's theorem since P (u) is bipartite of maximal degree ∆p.

-For 1 ≤ i ≤ n, L(s i (u)) = ∆ + p -1 and L(b) = 0 for any b ∈ 0≤i≤n B i (u).
Furthermore, for every 1 ≤ i ≤ n, label the vertices and edges of N i (u) as follows:

-L(s i (ū)) = 0; L(r i (u)) = ∆ + p -1; L(v) = ∆ + p -1 for v ∈ V i (u); L(t) = 0 for t ∈ T i (u) ; L(p 1 i (u)) = L(p 2 i (u)) = ∆ + p -3; L(q) = ∆ + p -2 for q ∈ Q i (u). -L(r i (u)s i (ū)) = p; label the edges of {r i (u)t | t ∈ T i (u)}∪{s i (ū)v | v ∈ V i (u)} with {p + 1, . . . , ∆ -1}; L(s i (u)p 1 i (u)) = 0; L(s i (u)p 2 i (u)) = 1; let q i (u) be a vertex of Q i (u); label p 1 i (u)q i (u) with 1, p 2 i (u)q i (u) with 0 and r i (u)q i (u) with p -1; label the edges of {pq | p ∈ {p 1 i (u), p 1 2 (u)}, q ∈ Q i (u) \ {q i (u)}} ∪ {r i (u)q | q ∈ Q i (u) \ {r i (u)}}
with {2, . . . , p -1}. This is possible by König's theorem. This is valid since ∆ ≥ p + 2 excpet that an edge r i (u)q with q ∈ Q i (u) \ {q i (u)} is labelled p -1 so conflicting with r i (u)q i (u). Hence we relabel the edge r i (u)q with 0.

If φ(u) is false, we label the vertices and the edges of P (u) and the N i (u) in the symmetric way, that is a label l when φ(u) is true is replaced by a label ∆ + p -1l when φ(u) is false.

Let us now label the edges and vertices of each clause subgraph for each clause C i . So far, the vertex s i (x) is label ∆ + p -1 if the literal x is true and 0 if x is false. Hence, since C i has one true and one false literal with φ, one vertex among s i (x i ), s i (y i ) and s i (z i ) is labelled ∆ + p -1 and another 0.

Suppose first that L(s i (x i )) = L(s i (y i )) = ∆ + p -1 and L(s i (z i )) = 0. Then label the vertices and edges of C(i) as follows:

-Label the vertices and edges of

C(i) \ (D 1 i ∪ D 2 i ∪ {s i (x)
, s i (y)} in the same way as N i (u) when φ(u) = f alse. In such a way L(w i ) = ∆ + p -1 and

L(r i w i ) = ∆ -1. -label the vertices of D 1 i ∪ D 2 i with ∆ + p -2. -Label the edges of {w i d | d ∈ D 1 i ∪D 2 i }∪{s(x i )d | d ∈ D 1 i }∪{s(y i )d | d ∈ D 2
i } with labels in {0, . . . , ∆p -1}. This is possible by König's theorem. Suppose now that L(s i (x i )) = ∆ + p -1 and L(s i (y i )) = L(s i (z i )) = 0. Then label the vertices and edges of C(i) as follows:

-Label the vertices and edges of

C(i) \ (D 1 i ∪ D 2 i ∪ {s i (x), s i (y)} in the same way as N i (u) when φ(u) = f alse. In such a way L(w i ) = ∆ + p -1 and L(r i w i ) = ∆ -1. -label the vertices of D 1 i ∪ D 2 i with ∆ + p -2. -Label the edges of {s(x i )d | d ∈ D 1 i } ∪ {w i d | d ∈ D 1 i } with labels in 0, . . . , ∆-p 2 -1 . This is possible by König's theorem. -Finally label the edges of {s(y i )d | d ∈ D 2 i } ∪ {w i d | d ∈ D 2 i } with labels in {p, . . . , ∆ -2}. This is possible by König's theorem because ∆-1-p ≥ ∆-p 2 for ∆ ≥ p + 2 and valid because p ≥ ∆-p 2 for ∆ ≤ 2p -1.
All the other cases are obtained from these two by symmetry of the graph and labels. This labelling may trivially be extended to the extra vertices and their incident edges to get a (p, 1)-total labelling of G(C, U).

Suppose now that there exists a (p, 1)-total labelling L of G(C, U) in {0, . . . , ∆+ p -1}. By Proposition 3 (i), for any u ∈ U, all the vertices s i (u), 1 ≤ i ≤ n, have the same label L u ∈ {0, ∆ + p -1} and all the vertices of n i=0 B i (u) are labelled with the integer Lu of {0, ∆ + p -1} \ L u . Moreover the edges of P (u) are labelled in {p, . . . , ∆ -1}. Since every vertex s i (u) has degree ∆p in P (u), each label of {p, . . . , ∆ -1} is assigned to an edge of P (u) incident to s i (u).

Let us now show that s i (ū) is assigned Lu . Without loss of generality, we may assume that L u = ∆ + p -1. Suppose for a contradiction that L(s i (ū)) = 0. By Proposition 3, L(s i (ū)) = ∆ + p -1 and so L(r i (u)) = 0 and L(t) = ∆ + p -1 for any t ∈ T i (u). Furthermore, the ∆p edges joining r i (u) to T i (u) ∪ s i (ū) are labelled in {p, . . . , ∆-1}. So each integer of this set label one of those edges. It follows that the edges of {r i (u)q | q ∈ Q i (u)} are labelled in {∆, . . . , ∆ + p -1}. Now each vertex q ∈ Q i (u) is labelled in {0, 1, ∆+p-1, ∆+p-2} by Proposition 3 (iii). So L(q) = 1 (0 is forbidden because of r i (u) and ∆+p-1 and ∆+p-2 by the edges qr i (u)). It follows that the edges of

{p 1 i (u)q | q ∈ Q i (u)} are labelled in Γ = {p+ 1, . . . , ∆ + p -1} \ {L(p 1 i (u)) -p + 1, . . . , L(p 1 i (u)) + p -1}. Hence L(p 1 i (u)) ≤ p otherwise |Γ| ≤ ∆-p-1 ≤ p-2 which is a contradiction. But L(s i (u)p 1 i (u)
) ∈ {0, . . . , p-1} because s i (u) is labelled ∆+p-1 and adjacent to an edge labelled l in P (u) for any l ∈ {p, . . . , ∆-1}. Thus L(s i (u)p 1 i (u)) = 0 and L(p 1 i (u)) = p. Analogously, we have L(s i (u)p 2 i (u)) = 0 which is a contradiction.

Hence s i (ū) is labelled Lu . Moreover, by Proposition 3, each label of {p, . . . , ∆-1} is assigned to an edge of

{vs i (u) | v ∈ {r i (u)} ∪ V i (u)}.
Let us define the truth assignment φ by φ(u) = true if L u = ∆ + p -1 and φ(u) = f alse if L u = 0. Let us show that each clause C i , 1 ≤ i ≤ n, has at least one true literal and at least one false literal. Suppose for a contradiction that the clause

C i = x i ∨ y i ∨ z i has all its literals true. Then s i (x i ) = s i (y i ) = s i (z i ) = ∆ + p -1.
In the same way as we proved that L(s i (ū)) is labelled Lu , we can prove that L(w i ) = 0. Now each edge of

{s i (x i )d | d ∈ D 1 i } is labelled in {∆, . . . , ∆+p-1} since s i (x i
) is adjacent to an edge labelled l for all l ∈ {p, . . . , ∆ -1}, either in P (x i ) if x i is a non-negated literal or in N i (u) if x i is the negated literal ū. Moreover, by Proposition 3 (iii), every vertex of D 1 i is labelled in {0, 1, ∆+p-2, ∆+p-1}. It follows that every vertex of D 1 i is labelled ∆+p-2. Analogously, we show that every vertex of

D 2 i is labelled ∆ + p -2. Hence the edges of F = {w i d | d ∈ D 1 i ∪ D 2 i } are assigned distinct labels in Γ ′ = {p, . . . , ∆ -2}. But |F | = 2p -2 > |Γ ′ | = ∆ -p -1
which is a contradiction. Proof: We reduce the problem to Not-All-Equal 3-SAT Problem. We need the following construction in order to emulate variables, clauses and negation.

Let C = {C 1 , . . . , C n } be a collection of clauses over a set U of variables. We will construct a graph G(C, U). For every variable u ∈ U, create a variable subgraph P u defined as follows:

V (P u ) = {a i (u) | 1 ≤ i ≤ n} ∪ {b i (u) | 1 ≤ i ≤ n} ∪ {s j (u) | 1 ≤ j ≤ n/2} E(P u ) = {a i (u)b i (u) | 1 ≤ i ≤ n} ∪ {a 2j-1 (u)s j (u) | 1 ≤ j ≤ n/2} ∪ {a 2j s j (u) | 1 ≤ j ≤ n/2} ∪ {a 2j+1 (u)s j (u) | 1 ≤ j ≤ n/2} . . . b 3 (u) b 4 (u) b n-2 (u) a n-2 (u) a 1 (u) a 3 (u) s 1 (u) s 2 (u) a 4 (u) an(u) a n-1 (u) b 2 (u) b n-1 (u) s (n-1)/2 (u) b 1 (u) a 2 (u) bn(u)
Fig. 9. The variable subgraph P u

For every clause C i = x ∨ y ∨ z, create a clause subgraph D i defined as follows:

V (D i ) = {a i (x), b i (x), a i (y), b i (y), a i (z), b i (z), c i , d i , t i (x), t i (y), v 1 i , v 2 i , w 1 i , w 2 i } E(D i ) = {a i (x)b i (x), b i (x)t i (x), a i (y)b i (y), b i (y)t i (y), a i (z)b i (z), b i (z)v 1 i , b i (z)v 2 i , c i d i , c i t i (x), c i t i (y), d i w 1 i , d i w 2 i , v 1 i w 1 i , v 2 i w 2 i }
If x is a non-negated literal u identify the vertices a i (u) and b i (u) of P u with the vertices a i (x) and b i (x) of D i .

c i d i b i (x) a i (y) b i (y) t i (y) t i (x) a i (x) a i (z) b i (z) v 1 i v 2 i w 2 i w 1 i Fig. 10. The clause subgraph D i
If x is a negated literal ū create four new vertices q 1 i (u), q 2 i (u), r 1 i (u), and r 2 i (u) and add the edges b

i (u)q 1 i (u), b i (u)q 2 i (u), q 1 i (u)r 1 i (u), q 2 i (u)r 2 i (u), r 1 i (u)a i (x) and r 2 i (u)a i (x).
Finally, add as many as necessary vertices of degree 1 adjacent to the vertices of

A = {a i (u), b i (u) | 1 ≤ i ≤ n, u ∈ U}∪{a i (x), b i (x), a i (y), b i (y), a i (z), b i (z), c i , d i , | C i =
x ∨ y ∨ z clause} so that they have degree p + 1 and to the vertices of

B = {w 1 i , w 2 i , | C i clause} ∪ {r 1 i (u), r 2 i (u)
| ū is a literal of C i } so that they have degree p. This is possible since p ≥ 3.

It is easy to check that G(C, U) is bipartite. One set of the partition contains the a i , d i , t i , v i , and q i , and the other contains the b i , s i , c i , w i and r i .

Let us prove now that G(C, U) has a (p, 1)-total labelling in {0, . . . , 2p} if and only if there is a truth assignment such that each clause in C has at least one true literal and at least one false literal. Suppose first that there exists a (p, 1)-total labelling L of G(C, U) in {0, . . . , 2p}.

By construction, every vertex of A has exactly one neighbour in A. Hence by Proposition 3, every vertex of A is labelled 0 or 2p and an edge with its two ends in A is labelled p. Furthermore, by Proposition 4 (v), for any variable u, the vertices a i (u), 1 ≤ i ≤ n, are labelled the same (either 0 or 2p) since the vertices a 2j-1 (u), a 2j (u) and a 2j+1 (u) have s j as a common neighbour. Hence we may define the truth assignment φ by φ(u) = true if L(a i (u)) = 2p and φ(u) = f alse if L(a i (u)) = 0. Let us prove that each clause in C has at least one true literal and at least one false literal under φ.

Let C i = x ∨ y ∨ z be a clause. Let t be one of its literals. If t is a non-negated literal u, then L(a i (t)) = L(a i (u)) since a i (t) = a i (u). If t is a negated literal ū then, according to Proposition 4 (vi), L(a i (t)) = L(b i (u)) = L(a i (u)). Hence to prove the result it suffices to prove that L(a i (x)), L(a i (y)) and L(a i (z)) are not all equal. Suppose (reductio ad absurdum) that they are all equal. Without loss of generality, we may suppose they are 0. Then since a i (x)b i (x), a i (y)b i (y) and a i (z)b i (z) are edges labelled p, then b i (x), b i (y) and b i (z) are labelled 2p. Now c i d i is also labelled p. By Proposition 4 (vi), d i and b i (z) are labelled the same. Thus d i is labelled 2p and so c i is labelled 0. Now c i and b i (x) have a common neighbour t i (x) so L(t i (x)c i ) = 2p according to Proposition 4 (iii). Analogously, L(t i (y)c i ) = 2p which is a contradiction.

Let us now suppose that there is a truth assignment φ such that each clause in C has at least one true literal and at least one false literal. For every variable u ∈ U, we do the following

-if φ(u) = true then, for 1 ≤ i ≤ n, set L(a i (u)) = 2p, L(b i (u)) = 0, L(a i (u)b i (u)) = p, and for 1 ≤ i ≤ n, L(s j (u)) = 2p -1, L(a 2j-1 s j (u)) = 0, L(a 2j s j (u)) = 1 and L(a 2j+1 s j (u)) = 2. -if φ(u) = f alse then, for 1 ≤ i ≤ n, set L(a i (u)) = 0, L(b i (u)) = 2p, L(a i (u)b i (u)) = p, andand for 1 ≤ i ≤ n, L(s j (u)) = 1, L(a 2j-1 s j (u)) = 2p, L(a 2j s j (u)) = 2p -1 and L(a 2j+1 s j (u)) = 2p -2.
For every literal

x of clause C i , set L(a i (x)) = 2p, L(b i (x)) = 0, L(a i (x)b i (x)) = p if φ(x) = true and set L(a i (x)) = 0, L(b i (x)) = 2p, L(a i (x)b i (x)) = p if φ(x) = f alse. Note that if x is a non-negated literal u then the vertices a i (x) = a i (u), b i (x) = b i (u) and the edge a i (x)b i (x) = a i (u)b i (u)
get the same label with the labelling of the clause and the labelling of the variable.

If x is a negated literal ū, then a i (x) and b i (u) are labelled the same. Hence if they are labelled 0, set L(q 1 i (u)) = L(q 2 i (u)) = 2, L(r 1 i (u)) = L(r 2 i (u)) = 1, L(b i (u)q 1 i (u)) = L(r 1 i (u)a i (x)) = L(q 2 i (u)r 2 i (u)) = 2p and L(b i (u)q 2 i (u)) = L(r 2 i (u)a i (x)) = L(q 1 i (u)r 1 i (u)) = 2p -1, and if they are labelled 2p, set L(q 1 i (u)) = L(q 2 i (u)) = 2p -2, L(r 1 i (u)) = L(r 2 i (u)) = 2p -1, L(b i (u)q 1 i (u)) = L(r 1 i (u)a i (x)) = L(q 2 i (u)r 2 i (u)) = 0 and L(b i (u)q 2 i (u)) = L(r 2 i (u)a i (x)) = L(q 1 i (u)r 1 i (u)) = 1.

Let us now extend the labelling to the clause graph D i . Since C i has one true literal and one false literal then {b i (x), b i (y), b i (z)} has one vertex labelled 0 and one is labelled 2p.

-If L(b i (x)) = L(b i (y)) = 0 and L(b i (z)) = 2p, set L(c i ) = 0, L(

d i ) = 2p, L(c i d i ) = p, L(t i (x)) = L(t i (y)) = 1, L(v 1 i ) = L(v 2 i ) = 2p -2, L(w 1 i ) = L(w 2 i ) = 2p-1, L(b i (x)t i (x)) = L(t i (y)c i ) = 2p, L(b i (y)t i (y)) = L(t i (x)c i ) = 2p -1, L(b i (z)v 1 i ) = L(w 1 i d i ) = L(v 2 i w 2 i ) = 0 and L(b i (z)v 2 i ) = L(w 2 i d i ) = L(v 1 i w 1 i ) =
(z)v 1 i ) = L(w 1 i d i ) = L(v 2 i w 2 i ) = 2p and L(b i (z)v 2 i ) = L(w 2 i d i ) = L(v 1 i w 1 i ) = 2p -1.
In other cases, we proceed analogously, since x and y are equivalent and by symmetry of the labelling l → 2pl.

Trivially, this labelling may be extended to the degree 1 vertices (added to ensure that elements of A and B have degree p + 1 and p) and their incident edges. 2

Conclusion

In this paper, we completely characterize the complexity of computing the (p, 1)-total labelling number when the graph is bipartite with respect to p and ∆. It would be interesting to do the same for k-regular graphs k-Regular (p, 1)-Total Labelling Problem: INSTANCE: k-regular graph G. QUESTION: What is λ p (G)?

When p = 1 McDiarmid and Sanchez-Arroyo [START_REF] Mcdiarmid | Total colouring regular bipartite graphs is NP-hard[END_REF] showed it to be NP-hard if k ≥ 3 and polynomial-time solvable otherwise.

When p ≥ 2, it remains unclear even if we expect some dichotomy NPhard/polynomial-time.

Havet and Yu [START_REF] Havet | 1)-total labelling of graphs[END_REF] showed that every 2-regular graph has (2, 1)-total labelling number 4. Moreover, they showed that for p ≥ 3, the (p, 1)-total number of a 2-regular graph is p + 3 if and only one of its components is an odd cycle. Otherwise it is p + 2. So for any p, one can find the (p, 1)-total number of a 2-regular graph in polynomial time.

If G is a connected 3-regular graph, by Proposition 1 (ii), λ 2 (G) ≥ 5. Moreover, Havet and Yu [START_REF] Havet | 1)-total labelling of graphs[END_REF] conjecture that λ 2 (G) = 5 unless G = K 4 . This would trivially imply that the 3-Regular (2, 1)-Total Labelling Problem is solvable in polynmial time.

Moreover one can determine in polynomial time the (3, 1)-total number of a 3-regular graph. Indeed if G is 3-regular then λ 3 (G) ≥ 6, by Proposition 1 (ii), λ 3 (G) ≤ 7 as proved by Havet and Yu [START_REF] Havet | 1)-total labelling of graphs[END_REF], and λ 3 (G) = 6 if and only if G is bipartite below.

  (i) λ p (G) ≥ ∆(G) + p -1. (ii) If G is regular and p ≥ 2 then λ p (G) ≥ ∆(G) + p. (iii) If p ≥ ∆(G), then λ p (G) ≥ ∆(G) + p.

Proposition 3

 3 Let p ≥ 2 and k ≥ p + 1 be an integer. Let G be a graph admitting a (p, 1)-total labelling L into {0, . . . , k + p -1}. (i) If d(v) = k, then either L(v) = 0 and its incident edges are labelled by {p, . . . , k + p -1} or L(v) = k + p -1 and its incident edges are labelled by {0, . . . , k -1}. (ii) If two vertices v and w of degree k are adjacent then L(vw) ∈ {p, . . . , k -1}. (iii) If p ≥ 3 and d

1 , 2

 12 k+p-2, k+p-1}. Then |{L(v)-p+1, . . . , L(v)+ p -1} ∩ {0, . . . , k + p -1}| ≥ p + 2. Hence at most k -2 labels are available to colour the edges adjacent to v. So d(v) ≤ k -2. (Note that this inequality does not hold if p = 2 since |{L(v) -1, L(v), L(v) + 1}| = 3.)Observe that none of the properties of Proposition 3 holds for p = 1; the graph I in Figure1provides a proof.

Fig. 1 .Proposition 4

 14 Fig. 1. The graph I Proposition 4 Let p ≥ 2 be an integer. Let G be a graph admitting a (p, 1)-

2 3 2 3. 1 A

 221 The case ∆ = 3 and p = polynomial-time algorithm for bipartite graphs

Theorem 3

 3 The following problem is NP-complete: INSTANCE: Graph G with maximum degree 3. QUESTION: Is λ 2 (G) = 4?Proof: We reduce the problem to Not-All-Equal 3-SAT Problem. We need the following construction in order to emulate variables, clauses and negation.

2 4Theorem 4

 24 NP-completeness of the bipartite (p, 1)-Total Labelling Problem 4.1 The case ∆ ≥ 2p If ∆ ≥ 2p ≥ 4, the ∆-Bipartite (p, 1)-Total Labelling Problem is NP-complete. Proof: We reduce the problem to the following NP-complete problem [9] (L03 in the book of Garey and Johnson [3]): Not-All-Equal (p + 1)-SAT Problem: INSTANCE: Set U of variables, collection C of clauses over U such that each clause C ∈ C has p + 1 literals. QUESTION: Is there a truth assignment such that each clause in C has at least one true literal and at least one false literal? Let C = {C 1 , C 2 , . . . , C n }, we construct a graph G(C, U) as follows: For each variable u, create the variable subgraph P (u) from the path b 0 (u)a 1 (u)b 1 (u)a 2 (u)b 2 (u) . . . a n (u)b n (u) by blowing up each a i (u), 1 ≤ i ≤ n, into a stable set A i (u) of cardinality p and each b i (u), 0 ≤ i ≤ n, into a stable set B i (u) of cardinality ∆-p odd and ∆-p 2 if i is even.

Fig. 5 .

 5 Fig. 5. The negation subgraph N i (u)

2 4. 2 1 Theorem 5

 2215 The case p + 2 ≤ ∆ ≤ 2p -If 2p -1 ≥ ∆ ≥ p + 2 ≥ 5, the ∆-Bipartite (p, 1)-Total Labelling Problem is NP-complete. Proof: We reduce the problem to Not-All-Equal 3-SAT Problem. Let C = {C 1 , C 2 , . . . , C n }, we construct a graph G(C, U) as follows: For each variable u, create the variable subgraph P (u) from the path b 0 (u)s 1 (u)b 1 (u)s 2 (u)b 2 (u) . . . s n (u)b n (u) by blowing up each b i (u) into a stable set B i (u) of cardinality ∆-p 2 if i is odd and ∆-p 2

2 4. 3 3 Theorem 6

 2336 The case ∆ = p + 1 and p ≥ Let p ≥ 3. The (p + 1)-Bipartite (p, 1)-Total Labelling Problem is NP-complete.

  1. -If L(b i (x)) = L(b i (z)) = 0 and L(b i (y)) = 2p, set L(c i ) = 2p, L(d i ) = 0, L(c i d i ) = p, L(t i (x)) = p, L(t i (y)) = 2p -1, L(v 1 i ) = L(v 2 i ) = 2, L(w 1 i ) = L(w 2 i ) = 1, L(c i t i (x)) = 0, L(t i (x)b i (x)) = 2p, L(c i t i (y)) = 1, L(t i (y)b i (y)) = 0, L(b i

  Theorem 7 Let p ≥ k ≥ 3 be integers. Let G be a k-regular graph. Thenλ p (G) = p + k if and only if G is bipartite. Proof: If G is bipartite, then by Proposition 2 (i), λ p (G) ≤ p + k.Suppose now that G has a (p, 1)-total labelling L of G in {0, . . . , p + k}. Then one can easily see that every vertex must receive colours in {0, 1, p+k-1, p+k}. Let A, (resp. B) be the set of vertices of H labelled with 0 or p + k -1, (resp. 1 or p + k). Then A and B are stable sets since the endvertices of an edge may not be labelled with 0 and p + k -1 or p + k and 1. So (A, B) is a bipartition of G.2

if i is

Partially supported by the european project FET-AEOLUS


Lasse Ullvén

Sylvain

Entretien Avec

Sylvain Racaud

Circulation du Finnish. Hardcore Punk

summers there were more opportunities to attend street parties and festivals. However, it wasn't until the summer of 2000 after moving to Tampere, the city that had been the "hardcore Mecca of Finland" in the early 1980s, that I would start building a more complete picture about what the punk subculture as a whole consisted of… Fast forward by about fifteen years, I had ended up studying popular culture at the University of Malta and was thinking about a subject for my Master's dissertation. Meanwhile I had lived in Brazil at a point for five years, and the subject of writing about the curious connections between Finnish and Brazilian punks dawned on me after my future supervisor advised me to write about something I love. The right choice of the subject gave me motivation to write, and I thought that I might as well keep writing, for as long as I could write about punk.

1. Pour les lecteurs qui ne seraient pas familiers avec la culture punk, peux-tu la présenter puis évoquer quelques champs théoriques qui l'étudient ?

For the readers who are not familiar with punk culture, can you present it and then evoke some theoretical fields that study it?

Punk is usually considered a musical style, and sometimes a sartorial style to go with the music, but that is only one aspect of the punk (sub)culture. To some it is indeed more about the superficial aspects, but to others it is a way of life, a community, a way to engage with your surroundings politically, a code through which you exist, and music to go along with that attitude. I will spare you the history parts about Ramones, Sex Pistols and so on, as these have been (almost too) well documented [START_REF] Legs | Please Kill Me : The Uncensored Oral History of Punk[END_REF]Savage 1991 and many others), and instead give my own take (there are practically as many takes as there are punks).

Punk is freedom to do whatever it is that you do, not limited to music, in the way that you see fit without caring what someone else is going to think about it. This often involves questioning and contesting the established norms and redefining values and assumptions. The nature of punk is extremely heterogeneous and there is no centralised authority that can determine whether something is punk in essence or isn't. Having said that, some of the global punk scene's gatekeepers seem to have a very limited idea of punk that they have outlined very strictly. The style of punk that I have written about is hardcore punk, a harsher take on the original idea which was conceived when in the late 1970s punk was starting to be watered down. There were many reasons for this watering down, one being the music industry's attempt to domesticate the punk spirit by commercialising it through what was called new wave. The reaction of the hardcore kids was to take punk into a new more radical direction. This meant musical extremity, often accompanied with a political charge.

How punk has been studied has changed over the years and nowadays I think it would even be possible to talk about punk studies as its own field; the following paragraph is just the tip of the iceberg of punk studies. Hebdige's Subculture (1979) is considered a starting point of sorts, but he was mostly reading into subcultural styles via semiotics, for example analysing the symbolism of the unorthodox use of the safety pin by the punks. Later on, he has been criticised, amongst other things, for the excessive use of theory and lack of empirical support for his ideas, but even so, with all its shortcomings, Hebdige's book has proven to have a remarkable longevity. In One Chord Wonders (1985), a book focussed entirely on punk, 2012). The point is that the subject is malleable and one is free to create connections in many directions. I used for example [START_REF] Jacques | Noise: The Political Economy of Music[END_REF] writings about the inherent connections between noise and politics, and the sanitisation of music. Another theory that I found useful for my purposes was [START_REF] Saito | Role of Imperfection in Everyday Aesthetics[END_REF] writings on the importance of imperfections. Personally however, I find the ethnography/personal experience approach to punk to be the most compelling one because it gives a voice to the punks instead of getting tangled in theory. This methodology has gained ground, I believe because most have realised how tricky (and often cringy) it is to mix punk and theory. Some (Dale 2012; Easley 2015) have even tried to use musicological theory, although this approach tends to show punk music in quite an unfavourable light, as the approach through musicology has tended to do with rock music in general [START_REF] Mcclary Susan | Start Making Sense! Musicology Wrestles with Rock[END_REF].

2. Comment le Finnish punk hardcore, originaire d'un pays qu'on peut considérer comme périphérique dans les années 1980 (situation géographie, langue), s'est-il diffusé au-delà de ses frontières, jusqu'au Brésil dès les années 1980 ?

How did the Finnish hardcore punk, originating from a country that can be considered as peripheral in the 1980s (geographical situation, language), spread beyond its borders, as far as Brazil in the 1980s?

First of all, there is something about the music made by the Finnish hardcore punks in the early 1980s that makes it stand out: originality, power, and even some quite catchy melodies. Not that all Finnish bands from that period sound the same, but there was a quantity of bands making passionate music along the same lines. In addition, it was done almost exclusively in their native language, which coincidentally suited the style and gave the music a unique character. The Finns had also picked up on the sign of the times and were making extreme punk, fast and aggressive, at the right time, when the style needed innovation and the ears of the listeners out in the punk world were ready for more abrasive sounds. Furthermore, some individuals in the scene that were not involved as musicians were working hard on distributing and releasing the music that the bands were producing. Due to the efforts of these people from micro sized labels and distribution operations the music ended up in the right places, and this was of great importance. Countless post packages filled with Finnish hardcore started to criss-cross all over the world. One of the places that showed an unusually high interest in Finnish hardcore was Brazil. But there were many other places where the music resonated. Interestingly, soap played a big role in these exchanges, as the punk custom was to soap the stamps so that the postmark could be later rubbed out, the stamps sent back and reused. Some of these packages were sent to important zines (such as Flipside, Maximumrocknroll and Ripper), a sort of early form of underground punk media through which information about the Finnish bands spread even to places where they lacked direct contacts.

So, what else made the music stand out? In my work I have pointed out a number of "transnational qualities" that potentially make the music of the Finnish bands resonate in different cultures and contexts, over different times. For one, despite the language barrier, the Finnish groups, and especially some of the vocalists, managed to transmit their feelings of anxiety and frustration through the ferociousness of their screams and their nervous musical delivery. I have suggested that one of the qualities of Finnish hardcore are these rough edges, or its "crumminess"; a jovial and child-like approach to music making which communicates to the listener a certain realness, transparency, vulnerability and unruliness. Another aspect of Finnish hardcore that was relatable and sympathy evoking across cultures was its jolly drunkenness. On the other hand, the self-destructive aspects of extreme drinking paradoxically added an apocalyptical seriousness to the sound. Finally, the fear of and resistance to war and oppression often evoked by Finnish bands are also universal sentiments.

3. Dans ce numéro, on s'appuie sur des travaux sur les inconspicuous globalization (Choplin et Pliez 2015), c'est-à-dire des traductions spécifiques, contextualisées de la globalisation, en marge de mouvements plus visibles. La dimension transnationale du Finnish punk hardcore évoque ces manifestations alternatives de phénomènes plus globaux. En quoi la circulation transnationale du Finnish punk hardcore nous renseigne-t-elle sur la production de souscultures, en particulier dans des pays du Global South, comme le Brésil où tu as vécu, ou bien la Malaisie ?

This issue draws on work on 'inconspicuous globalization' (Choplin and Pliez 2015), that is, specific, contextualized expressions of globalization on the margins of more visible movements. The transnational dimension of Finnish hardcore punk evokes these alternative manifestations of more global phenomena. How does the transnational circulation of Finnish hardcore punk inform us about the production of subcultures, especially in Global South countries, such as Brazil where you lived, or Malaysia? I wish I had been aware of "inconspicuous globalization" when I was writing my dissertation! It would have been an immensely useful term which perfectly describes the nature of the movements of Finnish hardcore, which would certainly qualify as a "small player", or as "globalization from below".

In fact, hardcore punk generally has thrived in the peripheries as will be addressed below in the discussion on punk spaces. When it comes to the influence of Finnish hardcore in the global peripheries, certainly an unusual form of globalization, I have used the example of groups, such as Brazilian group Helvetin Viemärit seen in figure 1, that have chosen to write their music in the Finnish language in order emulate and pay homage to the Finnish hardcore bands (Ullvén 2021a).

FIGURE 1 For this split 7", Helvetin Viemärit teamed up with Finnish hardcore legends Kuolema.

In the case of Brazil, it is very clear that Finnish hardcore played a part in influencing the local punk scene, however, that does not mean that Brazilian hardcore would sound, or even aim to sound the same. The influence goes beyond music itself for example to "philosophies" of punk music production, and the attitude of not caring about musical precariousness but rather embracing it.

Although this attitude can certainly be felt in some Finnish groups, it was also innate to the early groups from Brazil. At all accounts, that the Finns also subscribed to this attitude would have been inspirational to some Brazilians in the following decades. They were still experiencing similar challenges as some of the Finnish hardcore punks in the early 1980s: lack of spaces to practice, lack of spaces to perform, lack of access to musical education and equipment. One Brazilian interviewee (Ullvén 2016) used the example of the precariousness of the Finnish group Sorto to make the following point: listening to the group's single sided 7" from 1984 Aina valmiina, he could observe that these European punks had made this messy music with a precarious production and had pressed it on vinyl regardless of its imperfections, and this meant that the Brazilians could do it too despite the abovementioned lacks, and that the resulting music could even be considered all the better for it.

But even more importantly, the connections between Finnish and Brazilian punks show the importance of hardcore punk in the lives of people who live by it -the dedication to punk culture in every aspect of one's life. These people are so attuned to punk music that they feel what the Finnish punks were feeling -oppression, fear, anxiety, paranoia -despite intellectually the message is usually blocked by the language barrier. The Brazilian punks were able relate to the feelings because the same reasons that were already troubling the Finnish punks in the 1980s are still here: inequality, fear of war, oppression, injustice.

When it comes to Malaysia I cannot speak from personal experience, but listening to some of the local bands I quickly deduced that Finnish hardcore has been influential also in Malaysia.

Conveniently, discussing this country can take us to the next question about centre and periphery.

Dunn (2016) curiously uses Malaysia as an example about disparities that still exist in the global punk scene: that at any given time there would likely be an American or European group touring in Malaysia, while the contrary would be highly unlikely. However, around the time I was reading Dunn's book, I saw a Malaysian band play in Finland, and another one was due to visit later the same year. There is only one Finnish band that I know of that has made the trip in the opposite direction. This gives a completely different picture than Dunn's book, and evidence from the Finland -Brazil relations corroborates this view. When it comes to connections between Finland and Brazil, it certainly has not been a one-way street: although nowadays some Finnish bands visit Brazil with some regularity, the traffic in the opposite direction has also been intense in the last 20 years, and Brazilian bands found listeners in Finland already in the early 1980s.

4. Dans ta thèse, tu soulignes le « dilemma of hybrid cultures versus the centre/periphery » au sujet de l'expansion de la sous-culture du Finnish punk hardcore. Peux-tu expliquer cela pour les lecteurs indélicats qui n'auraient pas lu ta thèse ?

In your thesis, you point out the "dilemma of hybrid cultures versus the centre/periphery" about the expansion of the Finnish hardcore punk subculture. Can you explain this for the indelicate readers who would not have read your thesis?

If we think about popular culture, the tendency is that it spreads from the centre towards the peripheries, and of course initially it was so also for punk, since as a musical movement it was first defined around New York and London in the mid-1970s. However, as punk started to evolve, it took on different localised forms, and these short bursts of angry music, which to the casual listener might sound very similar at first, have their own characteristics which the adepts of the style recognise. In turn, these new takes on the style, as in the case of 1980s Finnish hardcore, for some reason or another, have garnered a reputation and gained followers also in the centre. Today, the hardcore punk fanatic from, say, New York, will undoubtedly be listening to large amounts of music produced outside their circle, and knowing bands for example from the global south (lately Colombia has been a hotspot for hardcore punk) is imperative, one of the ways in which this punk can show their "punkness", or as Thornton (1996) would have it, their "subcultural capital".

Still, O'Connor (2002) has seen that the bands and scenes from the centre are dominating the global scene, and the bands from the periphery are at a clear disadvantage. As an example, O'Connor mentions the disparity between Spanish bands that travel to play in Mexico, and the lack of a similar movements in the other direction. Be that as it may, this example does not give a complete picture of the global situation. As mentioned above, many Brazilian bands have toured and continue to tour in Europe, and also in the United States. On the other hand, although being positioned in the periphery may even give a given group an "edge" over another group from the centre, it is clear that those in the centre have, in addition to often having better material conditions, also a larger "punk infrastructure" around them and more access to records, concerts, contacts and so on. And then again, as the example of Finnish hardcore shows, there is the possibility to swim against the stream and make waves also in the centre (even if Finland would be considered "semi-peripheral" in this case). Still, the discussion on Finnish hardcore does not offer a definitive solution to this dilemma of hybrid cultures versus the centre/periphery view, but as a tentative conclusion I have referred to the point raised by Dines, Gordon & Guerra (2019) about the ebb and flow of relevance of different scenes.

5. Qu'est-ce que la circulation du punk hardcore finlandais nous apprend sur l'espace, sur les modèles de diffusion et sur les formes spatiales ? As-tu observé des formes spatiales communes et/ou spécifiques à travers tes nombreuses observations dans des sites et contextes variés ?

What does the circulation of Finnish hardcore punk tell us about space, patterns of diffusion, and spatial forms? Have you observed common and/or specific spatial forms through your many observations in various sites and contexts?

Granted, punk was conceived initially in the global centres, however, especially hardcore punk seems to have thrived in the peripheries. Of course, even hardcore initially began in the countries like the US and UK, and often California is offered as its birthplace (although there is an argument to be made for punk moving towards a more aggressive direction in different parts of the world simultaneously). However, if you zoom into the US and UK scenes at the time, the hardcore variants of punk began to pop up in cities other than the initial punk centres of London and New York. In the context of California, the first hardcore bands could be found in the outskirts of the greater Los Angeles area, in the periphery. On the east coast, places like Washington DC and Boston, although hardly small peripherical towns, were much more important hardcore cities in the early 1980s than New York was. When it comes to the UK, cities like Bristol (Disorder, Chaos UK) and Stoke-on-Trent (Discharge) produced more important hardcore bands than London. As mentioned above, in Finland, Tampere was the hardcore capital instead of Helsinki, and even some very small towns, such as Tornio in the north of the country, produced just as significant a crop of hardcore bands (Terveet Kädet, Rutto & Sorto) as the capital.

If you observe the situation today, punk has spread to most countries, and although the North American and European groups still have material advantages over the punks of the rest of the world, in the peripheries there is a different sort of realness that is out of reach for the the punks in the centre. I have suggested that punk is at its realest when it is having to overcome difficulties, and punk in this sense is also a way in which to build oppositional identities. [START_REF] Dunn | Never Mind the Bollocks: The Punk Rock Politics of Global Communication[END_REF] has stated that especially in the world peripheries, punk has been used as a tool against repressive social structures and regimes, and sees that 'there is far more at stake in the expression of a punk subculture in the global periphery than there is at the core' (p. 206).

When it comes to punk spaces, they are often found at the side-lines, however there is one central space where the punks make an appearance: the streets. Traditionally, weather allowing or not, punks can be seen loitering around the streets: bumming for coins, drinking, or just walking around aimlessly. Of course, in Finland, the extreme weather sets some limitations to how "street" the punks can get during the winter, but in places where the climate allows it, punks have been known to also sleep in the rough, often due to their homes being intolerant to their way of life (Spheeris 1998). This is one example of how seriously punks take their identity: they will sooner give up material comforts than make compromises with the way they want to live their lives.

Other punk spaces would be occupied houses also known as squats (and other forms of communal living). It has been traditionally the punk subculture that has, especially in Europe, sought to make use of abandoned buildings to a much greater extent than any other subcultures. I have yet to meet squatting metal heads, indie rockers or goths, but have visited dozens of punk squats around Europe, and some in South America. Usually, these places are about more than just making use of an abandoned space to live rent free; often the space is also shared with the (punk) community. There may be a do-it-yourself venue where bands can perform, or practice space for punk groups, a communal kitchen, workshops, screen printing facilities to make your own t-shirts and posters, perhaps even a communal garden to grow vegetables. There are squats with different levels of comfort (some have running water and electricity, others neither) and organisation (some incredibly dingy, others surprisingly clean). Not all punk spaces are squatted though, and other forms of communal living are houses that have been rented by a group of punks, sometimes even farmhouses where punks attempt to live off the land. Another form of punk dwelling that is not uncommon in central and southern Europe are caravans, sometimes grouped together to form a motley camp.

Although some punk squats have survived for around 40 years now, many have been evicted. Most squats do not have the chance to become established and are lost or abandoned for a myriad of reasons, one of which in the Finnish context again is the winter, as most abandoned buildings become unliveable. However, even short-lived or seasonal places have their value. In fact, Hakim Bey (1991) has argued that these spaces are at their freest, before excessive permanence, before the space becomes structured and begins to stifle individual creativity. Bey coined the term "temporary autonomous zones", and although he wasn't speaking only of these punk communities, his term captures something of the spirit of these punk spaces.

6. Ton travail est ethnographique, tu as mené des entretiens et des observations en Finlande (d'où tu es originaire) et dans des pays où le punk hardcore finlandais a suscité de l'engouement (Australie, Brésil, France, Grèce, Japon, etc.). Etant toi-même un membre actif de la scène punk hardcore, comment as-tu positionné cette expérience personnelle dans ta méthodologie de recherche ? Peux-tu en dire plus sur ton approche « 'punkness' of the research ».

Your work is ethnographic, you have conducted interviews and observations in Finland (where you are from) and in countries where Finnish hardcore punk has become popular (Australia, Brazil, France, Greece, Japan, etc.). Being yourself an active member of the hardcore punk scene, how did you incorporate this personal experience into your research methodology? Can you tell us more about your "punkness" of the research?

While I would have loved to visit the "field" also in Australia and Japan, unfortunately, my window into these scenes was created through video calls with members of the groups Hävittäjät (Figure 2) and Conclude respectively, as well as punk music from these countries, with a special focus on groups with clearly Finnish influences. In the other countries mentioned above, and further ones such as Spain and Finland, I conducted interviews with punks that listen to Finnish hardcore as well as taking up some "participant observation" at the local punk activities. Of course, the consumption of Finnish hardcore is not limited to the aforementioned countries, in fact, I have encountered fans of the style almost everywhere I have been, and where-ever there are punks, it seems that there is bound to be one of them that is a Finnish hardcore fanatic.

FIGURE 2 Members of the Australian group Hävittäjät have no ethnic ties to Finland, nevertheless they have opted to sing in the Finnish language.

Due to my personal involvement in the punk scene, I opted to use autoethnography as a part of my research methodology, however, hopefully not to the point of 'diary disease' (Bourdieu 2003), but just enough for it to be clear that I am not trying to come off as a neutral observer (if such a person exists). In addition, my personal experience was important in the following ways: having previously played in the countries was helpful, both in acquiring the necessary contacts, as well as already having an idea about the local scenes. Another punk-inspired decision I made was not to use Facebook (fb punx, fb punx, fb punx -f-off!), or other social media, to seek information, attract possible interviewees, make contacts, or whatever, however convenient that might have been (although these today could be counted as punk spaces, they are not my punk spaces).

In my case, the "punkness" of the research is not so much an organised research methodology, but rather a feeling. It includes relying on the punk network while conducting research. In practice this can mean for example sleeping on the sofa of the interviewee or at a gig venue instead of a hotel. This will result in a less remote experience. Punkness of the research should also mean listening to punk music; if the researcher studying punk culture for some reason does not already know punk music, it is imperative that they get listening! This listening should deepen their understanding of punk and to inspire thoughts. Furthermore, for example, relying on genuine punk sources like zines instead of what has been said about punk in mainstream media will certainly increase the punkness of the research. Furness ( 2012) has spoken about the punkness of research mostly through tell-tale signs that give away the non-punkness of the researcher.

7. La publication du savoir scientifique, par exemple la publication d'articles dans des revues scientifiques, s'appuie sur un processus d'évaluation rigoureux. Il existe des primes à l'excellence scientifique. Le monde scientifique est sélectif et on se prend beaucoup (trop) au sérieux. Tu montres de manière fine la contribution positive de l'imperfection « crumminess » dans la production de la sous-culture du Finnish punk hardcore, en Finlande et dans d'autres pays. Penses-tu que la positive contribution of imperfection aie sa place dans la production du savoir scientifique ?

The publication of scientific knowledge, for example the publication of articles in scientific journals, is based on a rigorous evaluation process. There are rewards for scientific excellence... The scientific world is selective and one takes oneself very (too) seriously. You show in a precise way the positive contribution of "crumminess" imperfection in the production of the Finnish hardcore punk subculture, in Finland and in other countries. Do you think that the positive contribution of imperfection has a place in the production of scientific knowledge?

In the case of Finnish hardcore punk, I have suggested that the "rawness", "crudity" or "crumminess" is an important part of the appeal of the music. It points to a devil-may-care attitude; to a lack of resources; to musical unscrupulousness. The rough edges in the music also give it a certain sincerity which is hard to achieve otherwise: its imperfections make it relatable. Errare humanum est, right? I have referred to [START_REF] Simon | Performing Rites: On the Value of Popular Music[END_REF] writings to illustrate this point in a more academic fashion, and from his discussion I found the term 'participatory discrepancies' which essentially differentiate the human musician, however good they may be, from a machine. The drunk Finnish hardcore punks attempting to play as fast as they could at the limit of their capabilities -under pressure since they often only had a few hours of studio time to capture and mix a recording -took these participatory discrepancies from slight to significant. This resulted in music that is human, all too human.

It is perhaps unadvisable, and at the very least difficult, to draw comparisons between making hardcore punk and producing scientific knowledge, however, I have to agree with the implication in the question: perhaps the academia may have something to learn from the punks. This observation has been made before: in Finland [START_REF] Blomstedt | Punkakatemia. Soundi Kirja[END_REF] picked up on this point already quite soon after the late 1970s punk explosion, and later on, in the realm of sociology David Beer (2014) has suggested that the discipline may be invigorated by taking notes from the punk ethos. In addition, as Saito (2017) has stated, appreciating imperfections is beneficial not only in order to enrichen our sense of aesthetics, but important also politically, socially and morally.

In a more day-to-day sphere of our personal lives one is time and time again amazed at how many positive contributions imperfections, and downright mistakes have had, and examples of some "unintentional rightness" are not unheard of even in the world of "hard science". Certainly, the contribution of mistakes has also been crucial when creating new products, some famous examples being corn flakes, Viagra and LSD. In these examples, the mistake created something for a different use than imagined, and of course, when it comes to music, the dynamic is different since it is about personal taste. All the same, errors in the performance created something that the learned musician would consider to be imperfect, but to the hardcore punks it was exactly what they were after. In the case of punk, mistakes also inevitably gave the final product some originality, since the are very difficult if not impossible to reproduce intentionally.

8. Tu as participé à une conférence organisée par le Punk Scholar Network en 2018 au Royaume Uni. Etait-ce punk ? Quels liens établis-tu entre création artistique et la production de savoir scientifique ou la création de cours ?

You presented a paper at a conference organized by the Punk Scholar Network in 2018 in the UK. Was it punk? What connections do you make between on the one hand creating art and on the other hand producing scientific knowledge or creating courses?

Yes, I was sceptical too upon arrival, but as soon as I met a couple of the organisers I immediately knew that they are punks. At this particular conference held at De Montfort University in Leicesterthe Punk Scholars Network has organised many other conferences that I didn't take part in -the focus was on hybridity, crossover and difference in punk and metal subcultures (figure 3). Imagine a lecture room full of freaks of different kinds that have an interest in punk, most often as a participant in the culture, but have also gotten involved in the academia, either as students or lecturers. Keeping in mind the heterogeneous nature of punk, the conference call easily be called a punk event.

Although not everyone there seemed like punks first and academics second, to many others that were present, punk is clearly a lifelong commitment which began before their involvement with the academia, and will continue beyond their stint at the university, however long that may be. Also, the chapter I contributed to a punk reader about Finnish hardcore and alcohol abuse came (Ullvén 2021b) about as a result of this conference.

FIGURE 3 The conference organisers from the Punk Scholars Network had made pins for the event.

When it comes to the connections between creating art (if punk qualifies) and producing scientific knowledge, ideally one can support the other. Creating punk music (or other kinds of art) may not only provide a counter balance and a retreat from the other end of the pendulum, but also help you in the creation of scientific knowledge by encouraging alternative solutions and mindsets when approaching problems. Punks are not often scientists, and scientists are not often punks (although some are without even knowing it), but both probably would have something to learn from each other.

9. Tu as joué dans un festival de heavy metal au Botswana. Au sujet de la diffusion en Afrique de cette culture de pays de l'Ouest, 4), I met participants from neighbouring countries, which does emphasise the fact that borders and nationalities are less important than the connection gained through listening to similar tunes. However, I cannot go as far as stating that the influence of heavy metal would have somehow abolished the borders and colonial legacies, and although some may have also placed their faith in metal music instead of organised religion, it would perhaps be imprudent to state it as a rule. Having said that, I was impressed with the dedication that the local people showed to rock and roll and heavy metal. The ambiance differed greatly from playing to blasé audiences in the European and North American capitals. It was much more inviting and much less judgemental. I can also agree with Banchs about heavy metal culture being empowering to some of its participants, however, there are always downsides and this extreme lifestyle may have led others astray.

FIGURE 4 Members of Overthrust, a death metal group from Botswana (from left to right): Spencer Thrust, Godfather, Vulture Thrust and Suicide Torment.

My trip to Botswana came about when two friends of mine had been there the previous year to begin work on a documentary called Freedom in the Dark (2018) about the local heavy metal scene. They were planning a second trip to conduct interviews at the Winter Metal Mania festival, which is held annually at the heart of the Kalahari region, in the city of Ghanzi. As it happens, I already had an ongoing musical project with one of these friends, a recording project that was never meant to leave the studio. However, I saw an opportunity that was not to be missed and proposed we introduce new members to the group in order to play a live show at the festival (figure 5).

FIGURE 5 In 2015, the line-up at Winter Metal Mania consisted of groups from Botswana, South Africa and Finland.

The group, Kirottu Ääni, ended up playing not only at the festival, but also in Botswana's capital Gaborone, and in the northern "rock city" of Maun (there is a video uploaded to Youtube from this occasion -https://www.youtube.com/watch?v=kP0nCX6Jc0U). The experience was overwhelmingly positive, although in my case, years spent in Brazil and trips elsewhere in South America had somewhat prepared me for performing in venues that may not be equipped to European standards.

In that sense, we can speak of centre and periphery and colonial legacies. What was very striking about some of the Botswana metalheads was how they had amalgamated some aspects of their local culture with heavy metal aesthetics. This was most obviously visible in the intricate costumes reminiscent of tribal ceremonial clothing, but made out of black leather and studs. But most importantly, I felt a magical feeling of genuineness that is perhaps only possible at the first moments of inspiration and enthusiasm when a scene is being formed. Everything felt fresh, and the people were so passionate about metal and rock music. The atmosphere allowed me to imagine how the Finnish punk scene may have felt like in its early stages, before excessive technology and access to good gear, before thinking about it too much and just doing it, before, before, before. I think about it nostalgically, even though (or because) I was not there in the 1980s.

10. Dans le chapitre "Love at first sip? When Finnish hardcore punk met alcohol" (Ullvén 2021b), tu écris "Overall, alcohol has been, and continues to be, an integral part of the Finnish punk scene." (p. 211). Comment cela se traduit-il dans les différents contextes où tu as pu mener tes enquêtes ?

In the chapter "Love at first sip? When Finnish hardcore punk met alcohol" (Ullvén 2021b), you wrote "Overall, alcohol has been, and continues to be, an integral part of the Finnish punk scene" (p. 211). How does this apply to the different contexts in which you have conducted your investigations?

As mentioned above, the drunkenness of the Finnish punks can be considered one of the "transnational qualities" of Finnish hardcore that many punks around the world can relate to. Overall, where ever there is a punk scene, you can bet there are a couple of heavy drinkers involved, and for most of the participants, some degree of drunkenness is assumed. Having said that, the Finns are infamous for their drinking habits in a scene that drinks quite heavily overall: Finland could be argued to have a greater concentration of these heavy drinkers in comparison to some other countries. Drunk to extremely drunk behaviour is common in Finnish punk shows, and in peak events, such as the Puntala Rock festival, extreme drinking is widespread and sustained throughout the weekend and beyond. Also, some Finnish touring bands are made up of quite infamous boozehounds whose exploits are the stuff of legend in many punk venues around Europe and around the world.

On the other hand, for example in Brazil, I have also witnessed some quite extreme cases of punkenabled alcohol abuse. Although the economic disparities between the two countries are quite extreme, in Brazil, the local sugar-cane booze is, or at least used to be, dirt cheap. It is not extremely difficult for any punk to be able to bum enough money for a litre of hard liquor if that is your goal, although often at concerts for example, many seem to have had to make the choice between getting drunk or paying to get into the show. Needless to say, many opt for getting drunk at the sidewalk outside the concert (while eyeballing for a chance to sneak in, not that some punks wouldn't do these kinds of things in Finland as well). Overall however the instances of extreme drunkenness in the Brazilian context are fewer in comparison to Finland. This could also have to do with, not only the drinking habits of the Finns, but the sense of self-preservation of the Brazilians: it would be less advisable to pass out on the sidewalk in Brazil than in Finland. Having said that, passing out on your way home in the wintertime is lethal in the Finnish context and unfortunately not unheard of (Ullvén 2021).

In any case, drinking is often part-and-parcel with the other punk activities where ever these activities take place, and as even some academic accounts [START_REF] Gololobov | Are we punks? -Yes, we drink!": The politics of drinking in a youth subculture[END_REF] have documented, this drinking sometimes gets extreme in other places as well. I could tell both happy and sad stories involving alcohol from personal experience, but in relation to punk music, and especially early 1980s Finnish hardcore, it is also important to note that alcohol has played a crucial role for many musicians. Drinking has helped in curbing stage-fright or studio nervousness, and at the same time influenced the performance, sometimes more, sometimes less depending on the quantity of alcohol consumed. Therefore, the effects of drinking can sometimes be actually heard on punk records, and more commonly, at live shows. Although today most punk groups take their music seriously, some still make it a point to pass out on or vomit on stage, or even if not reaching these ultimate extremes, at least give the impression that to the group drinking is the primary function and music is secondary, or even enabled by the alcohol.

Le mot de la fin est pour toi.

The last word is yours.

Although the Finnish hardcore bands wrote about many of the common punk topics such as how the system sucks, religion is bad, and cops are Nazi pigs, the songs about military service, war and nuclear apocalypse were so many that they became a Finnish hardcore cliché which the bands wishing to emulate the style were bound to repeat. In 2021 I ended my dissertation with remarks about the global increase in military expenditure, and how Discharge had juxtaposed this with the fact that "half the world is living in poverty" and "starving, dying of disease", in their song "Meanwhile" already over 40 years ago. Turns out (SIPRI 2022) that at the time of writing, global military expenditure was reaching a new record figure of $2 trillion (yes, that is 2 000 000 000 000 dollars). At this point Russia was still only gearing up to invade Ukraine. We can only imagine that this new war will also take the weapons trade (or "defence budgets" as they prefer to refer to it) to new heights.

Unfortunately, it seems that war songs never get old, quite the contrary. Instead, more war songs are justified by new wars. As important, correct and much-needed this resistance to war is, my fear is that the focus on war is side-tracking us from an even more crucial discussion when it comes to the survival of our species. There have always been wars, but it is the first time that we are dealing with a human-made climate crisis. Even if the nuclear weapons are never used, we are still headed for disaster. The Bulletin of the Atomic Scientists that since 1945 maintains the Doomsday Clock, which is an "indicator of the world's vulnerability to global catastrophe caused by manmade technologies" (Mecklin 2023), has, in 2023, moved the clock closer to apocalypse than it has ever been: 90 seconds to midnight. In their latest statement they maintain that although the war in Ukraine is the main cause for this move, it is evident that the war is "undermining global efforts to combat climate change" as well as the efforts to address other global concerns. When it comes to the punk scene, these global concerns have been, and continue to be important topics for songs, zine columns and conversations -punks have usually been quick to react to current issues and voice their grievances. But we are still a long way from hardcore punk songs about climate justice taking over from the ones about war and nuclear holocaust.

Inspiration to writing this interview was sought from:

Life:

  Ossification of Coral (Desolate Records 2020) Kansan Uutiset: Suomi orgasmin partaalla (Höhnie Records 2007) Masacre 68: No Estamos Conformes! (Masacre 68 self-released 1990) Kaos: Ayacucho Centro de Opresion (Sin Temores Records 2008) Overthrust / Katutura (Ecocentric Records 2018) VA -ABC Hardcore 82 (ABC Records 1994) Varaus: Tuomittu elämään (Varaus self-released 1983) Besthöven: Depois de um ataque aéreo (Noise Cat Records 2001)

  Laing used for example Walter Benjamin to analyse punk's "shock effects". Others have also used critical theory: Dunn (2016) used Benjamin in his book on Global Punk, and Moore (2010), in addition to Benjamin, also cites Adorno in his discussion about the withering of rock music's aura and how punk came to fill the vacuum left by this process.

1

Furthermore, there are studies on punk via gender

[START_REF] Leblanc | Pretty in Punk: Girl's Gender Resistance in a Boy's Subculture[END_REF]), via ethnicity (Duncombe & Tremblay 2011)

, discussions whether punk should be regarded a subculture or a post-subculture

[START_REF] Dylan | The Death and Life of Punk, the Last Subculture[END_REF][START_REF] David | Subcultures, Scenes or Tribes? None of the Above[END_REF]

, punk via its do-it-yourself ethos (Moore & Roberts 2009), and less obvious approaches like research on the connections between punk and alternative comedy (Bonello Rutter Giappone 2018). Of course, there are also many readings of punk politics (for a good example see Worley 2017), often via anarchism. Eventually, even Derrida has been used to analyse punk (Dale

You played in a heavy metal festival in Botswana. How did this happen? About the diffusion of this culture from Western countries in Africa, Edward Banchs (2022, p. 8) writes that this style produces new identities, new cultures, without borders, without religions, without colonial legacies, a non- condescending genre "a genre that empowers". What do you think about it?

  Edward Banchs (2022, p. 8) écrit que ce style produit de nouvelles identités, nouvelles cultures, sans frontières, sans religions sans héritages coloniaux, un genre non condescendant « a genre that empowers ». Qu'en penses-tu ?Based on my experience in Botswana, I can agree with Banchs about heavy metal creating new cultures and identities. In addition, at the Winter Metal Mania festival, organised by members of local death metal group Overthrust (figure

I have made references also to Horkheimer (Ullvén

2021a) and Marcuse (Ullvén 2016).