key: cord-0044044-uvod1hmv
authors: Bensmail, Julien; Fioravantes, Foivos; Nisse, Nicolas
title: On Proper Labellings of Graphs with Minimum Label Sum
date: 2020-04-30
journal: Combinatorial Algorithms
DOI: 10.1007/978-3-030-48966-3_5
sha: 83121b335ac64fe55e466632c2e41ac954bfec8a
doc_id: 44044
cord_uid: uvod1hmv

The 1-2-3 Conjecture states that every nice graph G (without component isomorphic to [Formula: see text]) admits a proper 3-labelling, i.e., a labelling of the edges with 1, 2, 3 such that no two adjacent vertices are incident to the same sum of labels. Another interpretation of this conjecture is that every nice graph G can be turned into a locally irregular multigraph M, i.e., with no two adjacent vertices of the same degree, by replacing each edge by at most three parallel edges. In other words, for every nice graph G, there should exist a locally irregular multigraph M with the same adjacencies and having few edges. We study proper labellings of graphs with the extra requirement that the sum of assigned labels must be as small as possible. That is, given a graph G, we are looking for a locally irregular multigraph [Formula: see text] with the fewest edges possible that can be obtained from G by replacing edges with parallel edges. This problem is quite different from the 1-2-3 Conjecture, as we prove that there is no k such that [Formula: see text] can always be obtained from G by replacing each edge with at most k parallel edges. We investigate several aspects of this problem. We prove that the problem of designing proper labellings with minimum label sum is [Formula: see text]-hard in general, but solvable in polynomial time for graphs with bounded treewidth. We also conjecture that every nice connected graph G admits a proper labelling with label sum at most [Formula: see text], which we verify for several classes of graphs.

In this paper, we consider proper labellings of graphs, a notion related to the 1-2-3 Conjecture, with the extra constraint that the sum of assigned labels must be minimised. For any notation on graph theory not defined here, we refer the reader to [7] . For a graph G, a function : E(G) → {1, . . . , k} is called a k-labelling of G. For any v ∈ V (G), let c (v) : V (G) → N * be the colour of v that is induced by , being the sum of labels assigned to the edges incident to v. That is, c (v) = u∈N (v) (vu) where N (v) = {u ∈ V (G) : uv ∈ E(G)} is the neighbourhood of v. We say that is a proper labelling if the resulting colouring c is a proper vertex-colouring of G, i.e., for every edge uv ∈ E(G) we have c (u) = c (v). Note that a graph admits a proper labelling if and only if it has no K 2 as a component [10] . Therefore, we here focus only on nice graphs, i.e., graphs without any component isomorphic to K 2 . Given a nice graph G, let χ Σ (G) be the smallest k such that G admits a proper k-labelling.

Maybe the most famous conjecture concerning proper labellings of graphs is the so-called 1-2-3 Conjecture, introduced by Karoński, Luczak and Thomason in 2004 [10] . This conjecture states that for every nice graph G, we have χ Σ (G) ≤ 3. It is worth noting that there exist nice graphs, such as nice complete graphs [5] , for which the upper bound is attained. Actually, given a graph G, deciding if χ Σ (G) ≤ 2 holds is an N P-complete problem [8] . The best currently known result towards the 1-2-3 Conjecture is that for any nice graph G, we have χ Σ (G) ≤ 5 [9] . Another important result states that the conjecture is satisfied for nice 3-colourable graphs [10] . Quite recently, a characterisation of nice bipartite graphs G with χ Σ (G) = 3 was provided in [13] . Moreover, χ Σ (G) ≤ 4 holds for every nice regular graph G [12] and χ Σ (T ) ≤ 2 holds for every nice tree T [5] .

Our work takes place in a recent series of works dedicated to better understanding proper labellings by studying variations with additional requirements, such as minimising the number of distinct colours [1] or minimising the maximum colour [4] induced by a proper k-labelling. An additional motivation is the following [6] . Given a graph G and a proper labelling of G, by replacing every edge e by (e) parallel edges, we obtain a multigraph M G, with the same adjacencies as G that is locally irregular, i.e., in which no two adjacent vertices have the same degree. In this setting, the 1-2-3 Conjecture states that, for every nice graph G, we can construct a corresponding M G, by replacing each edge by at most three parallel edges, and thus construct such an M G, with at most 3|E(G)| edges. One could argue however, that there might be cases in which it could be possible to obtain such a multigraph with fewer edges when being allowed to replace edges by more than three parallel edges. We study this through the following additional notions and definitions. Formally, for a labelling of a nice graph G, let σ( ) be the sum of labels assigned to the edges of G by . That is, σ( ) = e∈E(G) (e). For any k ≥ 1, let mE k (G) be the minimum value of σ( ) over all proper k-

Computing a proper labelling * such that σ( * ) = mE(G) is thus equivalent to finding a locally irregular multigraph M G, * with minimum number of edges.

Our Contributions. Section 2 starts by giving observations on labellings that are used to deduce the value of mE for nice complete bipartite graphs, complete graphs and cycles. We then exhibit an infinite family of graphs G showing that, for any fixed k ≥ 2, the value mE k (G) can be arbitrarily larger than mE k+1 (G), thereby establishing a fundamental property of our problem.

In Sect. 3, we study the complexity of computing the parameter mE k (G) for some input integer k and nice graph G. We establish both positive and negative results. On the negative side we prove that determining mE 2 (G) is N P-complete, even when G is restricted to a planar bipartite graph. An important point is that this is contrasting with the complexity of determining whether χ Σ (G) ≤ 2 holds for a given bipartite graph G, which can be done in polynomial time [13] . On the positive side, we prove that determining mE k (G) can be done in polynomial time whenever k is fixed and G is a graph with bounded treewidth.

Finally, Sect. 4 is dedicated to bounds on mE. Our guiding thread is a conjecture we raise, stating that, for any nice connected graph G, mE(G) ≤ 3 2 |E(G)| + O (1) . Towards this conjecture, we focus on the bipartite case. As support, we both provide infinite families of bipartite graphs G with "large" value of mE 2 (G), and prove the conjecture for several classes of bipartite graphs.

In this section, we give first insights into the problem of determining the parameters mE(G) and mE k (G) for a given graph G. We start off, in Sect. 2.1, by raising observations on labellings and by considering easy classes of graphs. For each G belonging to the classes we consider, we actually have mE k (G) = mE(G) for k = χ Σ (G). Put differently, a larger label than χ Σ (G) is not needed to achieve the smallest label sum. However, this behaviour is not systematic, as we exhibit, in Sect. 2.2, examples of trees T for which the smallest k such that mE k (T ) = mE(T ) is arbitrarily large.

First off, note that in general, labellings have systematic properties that can be useful to establish bounds on mE and mE k .

Let be a k-labelling of a graph G. The following items hold:

must therefore be an even number.

In particular, these observations allow to determine the value of mE for simple graph topologies, namely for complete bipartite graphs, complete graphs, and cycles. Due to lack of space, we only sketch the proof of the result about cycles. -if n ≡ 0 (mod 4), then mE(C n ) = mE 2 (C n ) = 3 2 |E(C n )|; -if n ≡ 1 or 3 (mod 4), then mE(C n ) = mE 3 (C n ) = 3 2 |E(C n )| + 1; -if n ≡ 2 (mod 4), then mE(C n ) = mE 3 (C n ) = 3 2 |E(C n )| + 3.

Sketch of Proof. The proof of the lower bounds follow mainly from the fact that, for any l ≤ k, any proper k-labelling of C n assigns label l to at most 1 2 |E(C n )| edges if n is odd and to at most 1 2 |E(C n )| − 1 edges if n ≡ 2 (mod 4). This claim is proved by considering the conflict graph that consists of one vertex per edge of C n , with two vertices being adjacent when the corresponding edges of C n cannot have the same label. We show that this conflict graph is either one cycle or two disjoint cycles (depending on the parity of n) and so the size of any of its independent sets (corresponding to a set of edges of C n that can receive the same label) is bounded above as required.

The upper bounds on mE are proven by giving a proper labelling matching the lower bound. For instance, if n ≡ 0 (mod 4), it is sufficient to alternate two consecutive edges labelled with 1, then two consecutive edges labelled with 2, and so on. When n ≡ 1 or 3 (mod 4), one single edge labelled with 3 is necessary and sufficient while two such edges are required and sufficient in the last case. ♦

In this section, we show that there is no absolute constant k ∈ N such that mE(G) = mE k (G) for all nice graphs. More precisely, for any integer k, we exhibit a tree T k such that mE(T k ) = mE k (T k ) < mE k−1 (T k ).

Let us first introduce the auxiliary graph A(α, β) (for α ≥ 2 and β ≥ 0), which will serve as the building block for T k . This auxiliary graph is a tree built recursively as follows. For any α * ∈ N, define A(α * , 0) as a leaf. For any β > 0, define A(α, β) as a tree of height β, rooted in a vertex r with α children. For each 1 ≤ i ≤ α, let c i be the corresponding child of r; each c i is the root of an A(α + i, β − 1) tree and thus d(c i ) = α + i + 1 (since each c i has α + i children of its own and an edge connecting it with his parent). Note that d(c i ) ∈ D(α) = [α + 2, 2α + 1] and that for i = j, we have d(c i ) = d(c j ) (and thus all values of D(a) are used exactly once). Finally, we say that A(α, β) is represented by r.

Let us also define the pending auxiliary graph that corresponds to A(α, β) as

with an extra vertex v connected to r. The vertex r is called the representative of P (α, β). The graph P (α, β) is said to be pending from v. Observe that P (α, β) is locally irregular and thus the labelling that assigns label 1 on every one of its edges is proper and mE(P (α, β)) = |E|.

Sketch of Proof. Let k ≥ 2 and let us describe the construction of T k . For 0 ≤ j ≤ k−1, let P (k+j, 2(k+1)) be the graph pending from v j that corresponds to an auxiliary graph A(k + j, 2(k + 1)) (represented by a vertex r j ) and let u, v be two adjacent vertices. The tree T k is the graph that is produced by merging v with each one of the v j . Observe that since r j represents A(k + j, 2(k + 1)), each r j has d(r j ) = k + j + 1 in T k and that the height of T k is 2(k + 1)

Let be the (k + 1)-labelling of T k that assigns label k + 1 to the edge uv and label 1 to the remaining edges of T k . It easy to see that is a proper

, at least one of the edges uv, r 0 w or vy has to have a label different from 1 for to be proper. Let us assume that (uv) = 1 (the other cases being similar). Let (uv) = l with 2 ≤ l ≤ k and assume that only this edge of T k has a label different from 1. Then c (v) = k + l and k + l ∈ [k + 2, 2k]. Recall that

Since uv is the only edge with a label different from 1, c (r j ) = d(r j ). It follows that there exists a j ∈ [0, k − 1], such that c (r j ) = c (v) leading to not being proper. Thus, there must exist another edge u v (with, say, u being the parent of v ) that is assigned a label different from 1 by . Note that this edge u v belongs to P (q, 2(k + 1)) (for some q ∈ [k, 2k − 1]) and either v = v or v is the child of the representative v of P (q, 2(k + 1)). It can be shown that, for to be proper, at least one child of u has one of its incident edges e assigned a label distinct from 1. This edge e belongs to some subtree P (q, 2k) and e is incident to either the representative of this copy of P (q, 2k) or to a child of this representative. Applying this argument recursively, it can be proved that, for to be proper, this copy of P (q, 2k) must contain at least k edges with a label greater than 1. Overall, mE(T k ) ≥ |E(T k )| + k + 1.

Observe that the height of T k can be freely controlled by changing the β value of the pending auxiliary graphs that form it. Furthermore, it follows from some of the arguments we have employed that mE(T (α, 2β)) < mE(T (α, 2β )) for β < β . Put simply, since the difference between mE k+1 (T k ) and mE k (T k ) depends on the height of T k and this can be an arbitrary number, the following holds:

This section is devoted to the complexity aspects of the problem of computing mE k . On the negative side, we prove that the problem is N P-complete in planar bipartite graphs. On the positive side, we prove that the problem can be solved in polynomial time for graphs with bounded treewidth, and that it is even FPT when parameterised by the treewidth plus the maximum degree.

Let us first introduce the k-gadget, for k ≥ 11, which will be useful for proving the main Theorem of this section. To build this gadget, start with k − 1 stars, each having a center denoted by

For each star, pick an arbitrary edge s i y i and identify all the y i into a single vertex y, which is called the representative of the gadget. Finally add another vertex u, called the root of the gadget, which is connected to y. It is clear that d(u) = 1 and d(y) = k. Also, each k-gadget is a tree with O(k 2 ) edges. Let v be a vertex of a graph G, and H be a k-gadget. The operation of adding H to G and identifying the root u of H with v is called attaching H to v.

Proof. The problem is clearly in N P. We focus on showing it is also N P-hard. The proof is done by reduction from Planar Monotone 1-in-3 SAT, which was shown to be N P-complete in [11] . In this problem, a 3CNF formula F is given as input, which has clauses with exactly three distinct variables all of which appear only positively. We say that a bipartite graph G = (V, C, E) corresponds to F if it is constructed in the following way: for each variable x i of F we add a variable vertex v i in V and for each clause C j of F we add a clause vertex c j in C. Then the edge v i c j is added if variable x i appears in clause C j . In the Planar Monotone 1-in-3 SAT problem, we also have that for any instance F the corresponding graph is planar. The question is whether there exists a 1-in-3 truth assignment of F ; that is a truth assignment to the variables of F such that each clause has exactly one variable with the value true.

Let us prove the statement for k = 2. Let F be the 3CNF formula with c clauses that is given as input to the Planar Monotone 1-in-3 SAT problem. Our goal is to construct a planar bipartite graph G such that F is 1-in-3 satisfiable if and only if mE 2 (G) ≤ |E(G)| + c.

Start with G = (V, C, E) being the planar bipartite graph that corresponds to F , with V being the set of the variable vertices v i , C being the set of the clause vertices c j and |C| = c. In F , each clause has exactly three variables but there is no bound on how many times a variable appears in F . Thus for each v i ∈ V, d(v i ) ≥ 1 and for each c j ∈ C, d(c j ) = 3. It follows that |V | ≤ 3c.

Modify G by adding the k-gadgets described earlier in the following way.

Thus the degree of each v i in G becomes equal to d v,i . On each clause vertex c j , attach c + 1 copies of the d c -gadget, c + 1 copies of the (d c + 2)-gadget and c + 1 copies of the (d c + 3)-gadget. Thus the degree of each c j in G becomes equal to d c . Clearly, the construction of G is achieved in polynomial time. Observe also that since G is planar and the attached gadgets are actually trees, G is also planar. Let be a proper 2-labelling of G such that σ( ) ≤ |E(G)| + c, i.e., there are at most c edges of G labelled 2 by . Observe that G contains p-gadgets for

Thus the above claim holds for each gadget attached to G.

Claim. For any proper 2-labelling of G with σ( ) ≤ |E(G)| + c, we have that:

Claim. Let be any proper 2-labelling of G with σ( ) ≤ |E(G)| + c. Then all edges of the attached gadgets must be labelled 1.

For every clause vertex c j , we have c (c j ) = {d c + 1}, which corresponds to two edges of G incident to c j labelled 1 and only one edge labelled 2.

We are now ready to show the equivalence between finding a 1-in-3 truth assignment φ of F and finding a proper 2-labelling of G such that σ( ) = mE 2 (G) ≤ |E(G)| + c. An edge v i c j of G labelled 2 (1, respectively) by corresponds to variable x i bringing truth value true (false, respectively) to clause C j by φ. Also, we know that in G , each variable vertex v i is adjacent to n ≥ 1 edges, all having the same label (either 1 or 2). Accordingly, the corresponding variable x i brings, by φ, the same truth value to the n clauses of F that contain it. Finally, in G , each clause vertex c j is adjacent to two edges labelled 1 and one labelled 2. This corresponds to the clause C j being regarded as satisfied by φ only when it has exactly one true variable.

The following theorem is proved by a classical (while non trivial) dynamic programming algorithm on tree-decompositions. Due to lack of space, we only state our main theorem. The full description of the algorithm and of its proof can be found in [3] . Importantly, the above theorem provides a constructive polynomial-time algorithm to compute mE k in the class of trees and in the class of odd multicacti (an important class in the context of the 1-2-3 Conjecture, that we detail below). Note however that k must be fixed and since, by Theorem 5, the smallest integer k such that mE(T ) = mE k (T ) for every tree T is not bounded, we leave open the question of the complexity of computing mE in the class of trees.

Recall that mE(G) ≤ χ Σ (G)|E(G)| and χ Σ (G) ≤ 5 (see [9] ) hold for every nice graph G. Thus mE(G) ≤ 5|E(G)| holds for every nice graph G, and even mE(G) ≤ 4|E(G)| holds when G is regular [12] . Moreover, for every graph satisfying the 1-2-3 Conjecture, even mE(G) ≤ 3|E(G)| holds. Throughout this section, we study how tight this bound is, in particular in the bipartite case.

Recall that bipartite graphs satisfy the 1-2-3 Conjecture [10] . For i ∈ {1, 2, 3}, let B i be the set of bipartite graphs G with χ Σ (G) = i. In particular, B 1 is the set of locally irregular bipartite graphs and the set B 3 is that of the so-called odd multi-cacti, which are defined as follows [13] . The set B 3 is exactly the set of graphs that can be obtained at any moment of the following procedure:

-Start from a cycle with length at least 6 congruent to 2 modulo 4 whose edges are properly coloured with red and green. -Repeatedly consider a green edge uv, and join u and v by a path of length at least 5 congruent to 1 modulo 4 whose edges are properly coloured with red and green, where the edge incident to u and that incident to v are red.

Proof. The statement trivially holds for every G ∈ B 1 since G is locally irregular and so mE(G) = |E(G)|. For every G ∈ B 2 (so G is not locally irregular), if we had mE 2 (G) = 2|E(G)|, then the only proper 2-labelling of G would be the one assigning label 2 to all edges, which can only be proper if G is locally irregular, a contradiction. Therefore, in any proper 2-labelling of G, there must be at least one edge assigned label 1, implying that mE(G) < 2|E(G)|. Let us now assume G ∈ B 3 , i.e., G is an odd multi-cactus with bipartition (U, V ) (both |U | and |V | are odd by construction). If G is a cycle with length at least 6 congruent to 2 modulo 4, then the result follows from Theorem 4. Thus, we may assume that the maximum degree Δ(G) of G is at least 3, i.e., some path attachments were made to build G starting from an original cycle.

Let us consider the last green edge xy to which a path P = (x, v 1 , . . . , v 4k , y) was attached in the construction of G, where k ≥ 1. Recall that d(x) = d(y) ≥ 3 by construction.

. This means that |V | is even. It is known that any bipartite graph with one part X of even size belongs to B 2 and furthermore admits proper 2-labellings where all vertices of X have odd colour while all vertices of the other part Y have even colour [5] . Therefore, there is a proper 2-labelling of G such that all vertices of U have even colour while all vertices of V have odd colour. Since x ∈ V , the colour c (x) is odd, and thus at least 3 since d G (x) ≥ 2. Similarly, v 4 ∈ V , so the colour c (v 4 ) is odd, and it is precisely 1 since d G (v 4 ) = 1.

We now extend to a proper 3-labelling of G, by assigning label 1 to v 1 v 2 , label 2 to xv 1 and v 3 v 4 , and label 3 to v 2 v 3 . This way, note that c (x) and

For these reasons, it should be clear that is indeed a proper 3-labelling of G. We additionally note that label 3 is actually assigned only once by , to v 2 v 3 . Furthermore, assigns label 1 at least once, e.g. to v 1 v 2 . From this, it follows that σ( ) ≤ 2|E(G)|.

Note that the upper bound in Theorem 8 is tight due to C 6 for which mE(C 6 ) = 12 = 2|E(C 6 )| (recall Theorem 4). However this seems to be a pathological case due to the small size of C 6 . For larger graphs, the next result shows that the upper bound can actually be improved.

Proof. Let U e (U o , respectively) be the set of vertices of U of even (odd, respectively) degree in G, and V e (V o , respectively) be the set of vertices of V of even (odd, respectively) degree in G. Note that either |U e | and |V o | must have the same parity, or |U o | and |V e | must have the same parity. This is because, otherwise, since |U | is even and |U | = |U e | + |U o |, the sizes |U e | and |U o | must have the same parity, we would get that also |V e | and |V o | have the same parity. Then we would deduce that u∈U d(u) ≡ v∈V d(v) (mod 2), which is not possible.

Without loss of generality, we may assume that U e and V o have the same parity, thus that |U e | + |V o | is even. Our aim now, is to design a 2-labelling of G that assigns label 2 on as few edges as possible, such that all vertices in U get an odd colour while all vertices in V get an even colour. Such a labelling will obviously be proper. To that aim, we proceed as follows. Let us start with assigning label 1 to all edges of G. This way, at this point the colour of every vertex is exactly its degree; so all vertices in U o and V e verify the desired colour property, while all vertices in U e and V o do not. To fix these vertices, we consider any spanning tree T of G. We now repeatedly apply the following fixing procedure: we consider any two vertices x and y of U e ∪ V o that remain to be fixed, and flip (i.e., turn the 1's into 2's, and vice versa) the labels of all edges on the unique path in T from x to y. This way, only the colours of x and y are altered modulo 2. Since |U e | + |V o | is even, there is an even number of vertices to fix, and, by flipping labels along paths of T , we can fix the colour of all vertices in U e ∪ V o . This results in a 2-labelling of G, with the desired properties, which is thus proper. Note now that assigns label 2 only to a subset of the edges of T . Since T has |V (G)| − 1 edges, the result follows.

The arguments in the proof of Theorem 9 actually generalise to graphs with larger chromatic number. See [3] for the proof details.

Theorem 10. Let G be a connected graph with chromatic number k = χ(G) at least 3. Then, we have mE(G) ≤ mE 2 k 2 +1 (G) ≤ |E(G)| + 2 k 2 |V (G)|.

We are not aware of graphs for which all proper 3-labellings require more than a few edges labelled with 3. In general, it might actually be true that, for all nice graphs, there is a proper 3-labelling with a few 3's where the number of 1's is about the number of 2's. Also, we observed, during experimentation via computer programs, that only small graphs G seem to have their value of mE(G) close to 2|E(G)| (recall that K 3 and C 6 are such examples, by Theorems 3 and 4). This leads us to conjecture the following:

There is an absolute constant c ≥ 1 such that, for every nice connected graph G, we have mE(G) ≤ 3 2 |E(G)| + c.

In the rest of this section, we investigate Conjecture 1 by giving a special focus to bipartite graphs. We exhibit several upper bounds for mE(G) in various subclasses of bipartite graphs. Each of these upper bounds support Conjecture 1. We also exhibit examples of graphs achieving these upper bounds.

Lower Bounds. We first show that it is not possible to lower mE(G) below the 3 2 |E(G)| barrier for general graphs G. This is already illustrated by Theorem 4, which states that mE(C n ) = 3 2 |E(G)| + 3 for every n ≡ 2 (mod 4). Note that these cycles C n are such that χ Σ (C n ) = 3. The lower bound even holds for bipartite graphs G with χ Σ (G) = 2. Indeed, there exist bipartite graphs for which label 2 must be assigned to at least half of the edges by any proper 2labelling. This is a consequence of the following more general result.

Theorem 11. There exist infinitely many bipartite graphs G ∈ B 2 with various structure verifying mE 2 (G) = 3 2 |E(G)|. This remains true for trees.

Sketch of Proof. Let G be any graph, and let H be a graph obtained from G by subdividing every edge e exactly n e times, where n e = 4k e + 3 for some k e ≥ 0. Then χ Σ (H) = 2. Furthermore, mE 2 (H) = 3 2 |E(H)|. Through our experimentation, we also managed to come up with the following class of bipartite graphs G for which mE 2 (G) slightly exceeds 3 2 |E(G)|. 

It is worth pointing out that a proper 2-labelling of a graph G where σ( ) is about 3 2 |E(G)| is actually a 2-labelling where the number of assigned 1's is about the same as the number of assigned 2's. Thus, Conjecture 1 relates to equitable proper labellings of graphs, introduced in [2] , which are proper labellings where, for every two assigned labels i, j, the number of edges assigned label i differs by at most 1 from the number of edges assigned label j. Regarding Conjecture 1, observe that mE 2 (G) ≤ 3 2 |E(G)| + 1 holds for every graph G admitting an equitable proper 2-labelling.

The authors in [2] proved that nice forests admit equitable proper 2labellings. This directly implies Theorem 13 below for trees with even size, while it does not for trees with odd size (as a 2-labelling where the number of assigned 2's is one more than the number of assigned 1's does not fulfill our claim), for which we need a dedicated proof. Recall that this result is optimal due to Theorem 11. When k = 0, i.e., T is a path, the claim is proved by performing a 1-extension or a 2-extension from a degree-1 vertex to the other so that more 1's than 2's are assigned. For larger values of k, the claim is proved by rooting T at some degree-1 vertex r, considering a branching vertex v at largest distance from r, and removing all pendant paths attached to v, resulting in a tree T . This tree T can be assumed to be nice (as otherwise there would be a better choice for r), and it thus admits, by induction, a proper 2-labelling assigning more 1's than 2's. It can then be proved that this labelling can be extended, by performing 1-extensions and 2-extensions, to the paths attached to v, resulting in a proper 2-labelling of T where more 1's than 2's are assigned.

Towards Conjecture 1, refined bounds can be deduced in particular contexts. For instance, any graph G satisfies |E(G)| + |V (G)| − 1 ≤ 3 2 |E(G)| as soon as |E(G)| ≥ 2|V (G)| − 2. As a consequence, Theorem 9 implies that a bipartite graph G ∈ B 2 with a part of even size verifies mE 2 (G) ≤ 3 2 |E(G)| as soon as G has minimum degree at least 4, or more generally when G is dense enough. The same holds for Hamiltonian bipartite graphs with a part of even size. Lemma 1. Let G be a Hamiltonian bipartite graph with bipartition (U, V ) where |U | is even. Then mE(G) ≤ mE 2 (G) ≤ 3 2 |E(G)|. Proof. Just mimic the proof of Theorem 9, but repair pairs of defective vertices of G along a Hamiltonian cycle C = (v 0 , . . . , v n−1 , v 0 ), matching each of them, say, with the next defective vertex in the ordering of C. If this fixing process turns more than half of the labels to 2, then, instead, repair pairs of vertices around C matching each of them with the previous defective vertex in the ordering (which is equivalent to flipping the labels along C).

The same result holds when G is bipartite and cubic (in which case χ Σ (G) = 2 since G ∈ B 2 , by definition of odd multi-cacti), by a more general argument: Lemma 2. Let G be a regular graph with χ Σ (G) = 2. Then mE 2 (G) ≤ 3 2 |E(G)|. Proof. Let be a proper 2-labelling of G. Since G is regular, the edges labelled 1 by , and similarly the edges labelled 2, must induce a locally irregular subgraph of G. Then the 2-labelling of G obtained by turning all 1's into 2's, and vice versa, is also proper. Now there is one of and that assigns label 2 to at most half of the edges, and the conclusion follows.

We have here studied the algorithmic complexity and bounds for the parameter mE. The main question we leave open is Conjecture 1 asking whether mE(G) ≤ 3 2 |E(G)| + O(1) holds for every nice connected graph G. We think that the proof of Theorem 9 could be improved to prove the conjecture for bipartite graphs.

Regarding our algorithmic results in Sect. 3, note that they all deal, for a given graph G, with the parameter mE k (G) (for some k), and not with the more general parameter mE(G). This is mainly because, as indicated by Theorem 5, in general there is no absolute constant that bounds, for all graphs G, the smallest k such that mE(G) = mE k (G). In particular, even for a graph G of bounded treewidth, although we can determine mE k (G) in polynomial time for any fixed k (due to our algorithm in Theorem 7), running enough iterations of our algorithm to determine mE(G) is not feasible in polynomial time. Thus, the question of determining the complexity of mE(G) is left open, even when G is a tree.

Edge weights and vertex colours: minimizing sum count

Equitable neighbour-sum-distinguishing edge and total colourings

On proper labellings of graphs with minimum label sum

On minimizing the maximum color for the 1-2-3 conjecture

Vertex-coloring edge-weightings of graphs

How to define an irregular graph

Graph Theory. Graduate Texts in Mathematics

On the complexity of vertex-coloring edge-weightings. Discrete Math

Vertex-coloring edge-weightings: towards the 1-2-3-conjecture

Edge weights and vertex colours

Minimum-weight triangulation is NP-hard

The 1-2-3 conjecture almost holds for regular graphs

The 3-flow conjecture, factors modulo k, and the 1-2-3-conjecture