Julien Bensmail

Foivos Fioravantes

Fionn Mc

On the Role of 3s for the 1-2-3 Conjecture *

Keywords: Proper labellings, 3-chromatic graphs, 1-2-3 Conjecture

The 1-2-3 Conjecture states that every connected graph different from K2 admits a proper 3-(edge-)labelling, i.e., can have its edges labelled with 1, 2, 3 so that no two adjacent vertices are incident to the same sum of labels. In connection with some recent optimisation variants of this conjecture, in this paper we investigate the role of the label 3 in proper 3-labellings of graphs. An intuition from previous investigations is that, in general, it should always be possible to produce proper 3-labellings assigning label 3 to a only few edges.

We prove that, for every p ≥ 0, there are various graphs needing at least p 3s in their proper 3-labellings. Actually, deciding whether a given graph can be properly 3-labelled with p 3s is NP-complete for every p ≥ 0. We also focus on classes of 3-chromatic graphs. For various classes of such graphs (cacti, cubic graphs, triangle-free planar graphs, etc.), we prove that there is no p ≥ 1 such that all their graphs admit proper 3-labellings assigning label 3 to at most p edges. In such cases, we provide lower and upper bounds on the number of 3s needed.

Introduction

This work is mainly motivated by the so-called 1-2-3 Conjecture, which can be defined through the following terminology and notation. Let G be a graph and consider a k-(edge-)labelling : E(G) → {1, . . . , k}, i.e., an assignment of labels 1, . . . , k to the edges of G (from here on, the term "edge-" will be dropped). To every vertex v ∈ V (G), we can associate, as its colour c (v), the sum of labels assigned by to its incident edges. That is, c (v) = u∈N G (v) (vu). We say that is proper if c (u) = c (v) for every uv ∈ E(G), that is, if no two adjacent vertices of G are incident to the same sum of labels by .

It turns out that K 2 , the complete graph on two vertices, is the only connected graph admitting no proper k-labellings (for any k ≥ 1) [START_REF] Karoński | Edge weights and vertex colours[END_REF]. In other words, any connected graph with at least three vertices admits a proper k-labelling (for some k ≥ 1). Thus, when investigating the 1-2-3 Conjecture, we generally focus on nice graphs, which are those graphs with no connected component isomorphic to K 2 , i.e., admitting proper labellings. If a graph G is nice, then we can investigate the smallest k ≥ 1 such that proper k-labellings of G exist. This parameter is denoted by χ Σ (G).

A natural question to ask, is whether this parameter χ Σ (G) can be large for a given nice graph G. This question is precisely at the heart of the 1-2-3 Conjecture:

1-2-3 Conjecture (Karoński, Łuczak, Thomason [START_REF] Karoński | Edge weights and vertex colours[END_REF]). If G is a nice graph, then χ Σ (G) ≤ 3.

To date, most of the progress towards the 1-2-3 Conjecture can be found in [START_REF] Seamone | The 1-2-3 Conjecture and related problems: a survey[END_REF]. Let us highlight that the conjecture was verified mainly for 3-colourable graphs [START_REF] Karoński | Edge weights and vertex colours[END_REF] and complete graphs [START_REF] Chang | Vertex-coloring edge-weightings of graphs[END_REF].

Regarding the tightness of the conjecture, it was proved that deciding if a given graph G verifies χ Σ (G) ≤ 2 is NP-complete in general [START_REF] Dudek | On the complexity of vertex-coloring edge-weightings[END_REF], and remains so even in the case of cubic graphs [START_REF] Dehghan | Algorithmic complexity of proper labeling problems[END_REF]. This means that recognising graphs admitting proper 2-labellings (or, the other way around, of graphs needing 3s in their proper 3-labellings) cannot be done in polynomial time unless P=NP. Lastly, to date, the strongest result towards the 1-2-3 Conjecture is that χ Σ (G) ≤ 5 for every nice graph G [START_REF] Kalkowski | Vertex-coloring edge-weightings: Towards the 1-2-3-conjecture[END_REF].

This work follows a recent line of research dedicated to studying optimisation problems related to the 1-2-3 Conjecture which arise when investigating the existence of proper labellings fulfilling additional constraints. In a way, one of the main sources of motivation here is to further understand the very mechanisms that lie behind proper labellings. In particular, to better understand the connection between proper labellings and proper vertex-colourings, the authors of [START_REF] Baudon | Edge weights and vertex colours: Minimizing sum count[END_REF][START_REF] Bensmail | On minimizing the maximum color for the 1-2-3 Conjecture[END_REF] studied proper labellings for which the resulting vertex-colouring c is required to be close to an optimal proper vertex-colouring (i.e., with the number of distinct resulting vertex colours being close to the chromatic number). It is also worth mentioning the work done in [START_REF] Bensmail | On proper labellings of graphs with minimum label sum[END_REF], where proper labellings minimising the sum of labels assigned to the edges were investigated.

Each of these previous investigations led to presumptions of independent interest. In particular, it is believed in [START_REF] Bensmail | On minimizing the maximum color for the 1-2-3 Conjecture[END_REF], that every nice graph G should admit a proper labelling where the maximum vertex colour is at most 2∆(G) (recall that ∆(G) and δ(G) are used to denote the maximum and the minimum degree, respectively, of any vertex of G), while, from [START_REF] Bensmail | On proper labellings of graphs with minimum label sum[END_REF], it is believed that every nice graph G should admit a proper labelling where the sum of assigned labels is at most 2|E(G)|. One of the main reasons why these presumptions are supposed to hold, is the fact that, in general, it seems that nice graphs admit 2-labellings that are almost proper, in the sense that they only need a few 3s to design proper 3-labellings. Note that, if this was true, then indeed the presumptions from [START_REF] Bensmail | On minimizing the maximum color for the 1-2-3 Conjecture[END_REF] and [START_REF] Bensmail | On proper labellings of graphs with minimum label sum[END_REF] above would be likely to hold. It is also worth mentioning that this belief on the number of 3s is actually a long-standing one of the field, as, in a way, it lies behind the 1-2 Conjecture raised by Przybyło and Woźniak [START_REF] Przybyło | On a 1,2 conjecture[END_REF], which states that we should be able to build a proper 2-labelling of every graph if we are additionally allowed to locally alter every vertex colour a bit.

Our goal in this work is to study and formally establish the intuition that, in general, graphs should admit proper 3-labellings assigning only a few 3s. We study this through two questions.

• The very first question to consider is whether, given a (possibly infinite) class F of graphs, the members of F admit proper 3-labellings assigning only a constant number of 3s, i.e., whether there is a constant c F ≥ 0 such that all graphs of F admit proper 3-labellings assigning label 3 to at most c F edges. Note that this is something that is already known to hold for a few graph classes. For instance, all nice trees admit proper 2-labellings, thus proper 3-labellings assigning label 3 to no edge [START_REF] Chang | Vertex-coloring edge-weightings of graphs[END_REF]. Similarly, from results in [START_REF] Bensmail | On proper labellings of graphs with minimum label sum[END_REF], it can be deduced that all nice bipartite graphs admit proper 3-labellings assigning label 3 to at most two edges.

• In case F admits no such constant c F , i.e., the number of 3s the members of F need in their proper 3-labellings is a function of their number of edges, the second question we consider is whether the number of 3s needed must be "large" for a given member of F, with respect to the number of its edges.

Throughout this work, we investigate these two questions in general and for more restricted classes of graphs. We start off in Section 2 by formally introducing the terminology that we employ throughout this work to treat these concerns, and raising preliminary observations and results. Then, in Section 3, we introduce proof techniques for establishing lower and upper bounds on the number of 3s needed to construct proper 3-labellings for some graph classes. In Section 4, we use these tools to establish that, for several classes of graphs, the number of 3s needed in their proper 3-labellings is not bounded by an absolute constant. In such cases, we exhibit bounds (functions depending on the size of the considered graphs) on this number.

Terminology, preliminary results, and a conjecture

Let G be a graph and G be a subgraph of G (i.e., created by deleting vertices and/or edges of G). For any vertex v ∈ V (G), let N G (v) = {u ∈ V (G) : uv ∈ E(G)} denote the neighbourhood of v in G, and let d G (v) = |N G (v)| denote the degree of v in G. Furthermore, recall that a subgraph G is induced if it can be created only by deleting vertices of G. That is, for each edge uv ∈ E(G), if u, v ∈ V (G ), then uv ∈ E(G ).

Let G be a graph and c : V (G) → {1, . . . , k} be a k-vertex-colouring of G. If, for every edge uv ∈ E(G), we have that c(u) = c(v), then we say that c is a proper k-vertex-colouring of G. Furthermore, the chromatic number χ(G) is defined as the minimum k such that there exists a proper k-vertex-colouring of G. Finally, recall that a graph

G is k-chromatic if χ(G) = k and k-colourable if χ(G) ≤ k.
Note that the same terminology can be used for families of graphs as well. For any additional notation on graph theory not defined here, we refer the reader to [START_REF] Diestel | Graph Theory[END_REF].

Proper 3-labellings assigning few 3s

Let G be a (nice) graph, and be a k-labelling of G. For any i ∈ {1, . . . , k}, we denote by nb (i) the number of edges assigned label i by . Focusing now on proper 3-labellings, we denote by mT(G) the minimum number of edges assigned label 3 by a proper 3-labelling of G. That is,

mT(G) = min{nb (3) : is a proper 3-labelling of G}.
We extend this parameter mT to classes F of graphs by defining mT(F) as the maximum value of mT(G) over the members G of F. Clearly, mT(F) = 0 for every class F of graphs admitting proper 2-labellings (i.e., χ Σ (G) ≤ 2 for every G ∈ F).

Given a graph class F, we are interested in determining whether mT(F) ≤ p for some p ≥ 0. From this perspective, for every p ≥ 0, we denote by G p the class of graphs G with mT(G) = p. For convenience, we also define

G ≤p = G 0 ∪ • • • ∪ G p .
As it was proved, for instance in [START_REF] Chang | Vertex-coloring edge-weightings of graphs[END_REF], that nice trees admit proper 2-labellings, if we denote by T the class of all nice trees, then the terminology above allows us to state that T ⊂ G 0 . More generally speaking, bipartite graphs form perhaps the most investigated class of graphs in the context of the 1-2-3 Conjecture. A notable result, due to Thomassen, Wu, and Zhan [START_REF] Thomassen | The 3-flow conjecture, factors modulo k, and the 1-2-3-conjecture[END_REF], is that, for any bipartite graph G, χ Σ (G) = 3 if and only if G is an odd multi-cactus, where odd multi-cacti form a particular class of 2-edge-connected bipartite graphs obtained through pasting cycles with certain lengths onto each other in a particular way. This specific class of graphs was further studied in several works, such as [START_REF] Bensmail | On proper labellings of graphs with minimum label sum[END_REF], in which it was proved that odd multi-cacti admit proper 3-labellings assigning label 3 at most twice.

Theorem 2.1 (Bensmail, Fioravantes, Nisse [START_REF] Bensmail | On proper labellings of graphs with minimum label sum[END_REF]).

If G is a nice bipartite graph, then G ∈ G ≤2 . More precisely, G ∈ G 0 if G is not an odd multi-cactus, G ∈ G 2 if G is a cycle of length congruent to 2 modulo 4, and G ∈ G 1 otherwise (i.e., if G is an odd multi-cactus different from a cycle C 4k+2 ).
Theorem 2.1 is worrisome in the sense that, even without considering any additional constraint, we do not know much about how proper 3-labellings behave beyond the scope of bipartite graphs. Our take in this work is to focus on the next natural case to consider, that of 3-chromatic graphs, which fulfil the 1-2-3 Conjecture [START_REF] Karoński | Edge weights and vertex colours[END_REF]. Unfortunately, as will be seen later on, a result equivalent to Theorem 2.1 for 3-chromatic graphs does not exist, even for very restricted classes of 3-chromatic graphs (e.g., cacti, cubic graphs, triangle-free planar graphs, etc.).

Regarding the classes G 0 , G 1 , . . . , it is worth mentioning right away that each G p is wellpopulated, in the sense that there exist infinitely many graphs, with various properties, belonging to G p . Actually, it turns out that deciding whether a given graph G belongs to G ≤p is NP-complete for every p ≥ 0. We postpone the proofs of these statements to Section 3 (Observation 3.3 and Theorem 3.4), as they require the tools and results introduced earlier in the same section.

As mentioned earlier, we will see throughout this work that, for several graph classes F, there is no p ≥ 0 such that F ⊂ G ≤p . For such a class, we want to know whether the proper 3labellings of their members require assigning label 3 many times, with respect to their number of edges. We study this aspect through the following terminology. For a nice graph G, we define ρ 3 (G) = mT(G)/|E(G)|. We extend this ratio to a class F by setting ρ 3 (F) = max{ρ 3 (G) : G ∈ F}.

In this work, we are thus interested in determining bounds on ρ 3 (F) for some graph classes F of 3-chromatic graphs, and, more generally speaking, in how large this ratio can be. Note that this is similar to considering how large ρ 3 (G) can be for a given graph G. Also, notice that graphs G of small size with χ Σ (G) = 3 are more likely to require many (compared to |E(G)|) 3s to be properly 3-labelled, resulting in these graphs having "large" ρ 3 (G) (meaning a value close to 1). Through an exhaustive search, it is easy to see that, among the sample of small connected graphs (e.g., of order at most 6), the maximum ratio ρ 3 is exactly 1/3, which is attained by C 3 and C 6 . As will be seen through the next sections, at the moment, these are the worst graphs we know of, which leads us to raising the following conjecture.

Conjecture 2.2. If G is a nice connected graph, then ρ 3 (G) ≤ 1/3.
It is worth adding that Conjecture 2.2 can be seen as a sort of weaker version of an equitable version of the 1-2-3 Conjecture, investigated in [START_REF] Baudon | Equitable neighbour-sum-distinguishing edge and total colourings[END_REF][START_REF] Bensmail | Further results on an equitable 1-2-3 conjecture[END_REF]. In that version, it is believed that, a few exceptions apart, every graph should admit a proper 3-labelling where all labels are assigned about the same number of times, i.e., the absolute value of the difference between nb (i) and nb (j) is at most 1 for any two assigned labels i, j. Such a labelling is called equitable.

We actually cannot benefit much from the results in [START_REF] Baudon | Equitable neighbour-sum-distinguishing edge and total colourings[END_REF][START_REF] Bensmail | Further results on an equitable 1-2-3 conjecture[END_REF] since most of these results are about equitable proper 3-labellings of classes of bipartite graphs, while bipartite graphs form a pretty well-understood case in our context (recall Theorem 2.1). One result we do get from [START_REF] Baudon | Equitable neighbour-sum-distinguishing edge and total colourings[END_REF] is an upper bound on ρ 3 for complete graphs, which is actually improved by another result (see Section 5).

General results on proper labellings

In this subsection, we prove results on proper labellings, which will be useful in the next sections.

Observation 2.3. Let G be a graph containing two adjacent vertices v 2 and v 3 of degree 2. Let v 1 be the other neighbour of v 2 , and let v 4 be the other neighbour of v 3 (possibly v 1 = v 4 ). Then, by any proper labelling of G, we have

(v 1 v 2 ) = (v 3 v 4 ).
Proof. Since, by any proper labelling of G, we have that c

(v 2 ) = (v 1 v 2 ) + (v 2 v 3 ), c (v 3 ) = (v 2 v 3 ) + (v 3 v 4 ), and c (v 2 ) = c (v 3 ), then (v 1 v 2 ) = (v 3 v 4 ).
Let be a k-labelling of some graph, and let σ : {1, . . . , k} → {1, . . . , k} be a permutation of {1, . . . , k}. We denote by sw( , σ) the k-labelling obtained from by switching labels as indicated by σ. That is, if (e) = i for some edge e and label i, then sw( , σ)(e) = σ(i). Assuming the set of labels {1, . . . , k} is clear from the context, for any two i, j ∈ {1, . . . , k}, we denote by σ i↔j the permutation only swapping labels i and j. That is, σ i↔j (i) = j, σ i↔j (j) = i, and σ i↔j (l) = l for every l ∈ {1, . . . , k} \ {i, j}.

Let G be a connected graph.

If every vertex v ∈ V (G) satisfies d G (v) = d, then G is d-regular. Furthermore, if every vertex v ∈ V (G) satisfies d G (v) ∈ {1, d}, then we say that G is quasi d-regular.
It is clear that every graph that is d-regular, is also quasi d-regular. Lemma 2.4. If is a proper 3-labelling of a quasi d-regular graph G, then sw( , σ 1↔3 ) is also proper.

Proof. Assume G is quasi d-regular for some d ≥ 2, and set = sw( , σ 1↔3 ). Observe that, by a k-labelling, a vertex of degree 1 can never be involved in a colour conflict with its neighbour (this is true because all labels assigned by a k-labelling are, by definition, positive). Consider any edge

vw ∈ E(G) with d G (v) = d G (w) = d. For 1 ≤ i ≤ 3, let n i be the number of edges incident to v that are labelled i by . Then, n 1 + n 2 + n 3 = d, c (v) = n 1 + 2n 2 + 3n 3 , and c (v) = 3n 1 + 2n 2 + n 3 , and thus, c (v) + c (v) = 4(n 1 + n 2 + n 3 ) = 4d. Similarly, we have that c (w) + c (w) = 4d. Therefore, c (v) -c (w) = c (w) -c (v), with c (v) = c (w) (since is a proper labelling) implying that c (w) = c (v). It follows that is a proper 3-labelling of G.
Analogously, one can prove: Observation 2.5. If is a proper 2-labelling of a quasi 3-regular graph, then sw( , σ 1↔2 ) is also proper. In G, the white vertices can have arbitrarily many neighbours in the grey part, while the full neighbourhoods of the black vertices are as displayed. In H, the white vertices are the border vertices, while the black vertices are the core vertices.

3 Tools for establishing bounds on mT and ρ 3

Weakly induced subgraphs -A tool for lower bounds

Most of the lower bounds on mT and ρ 3 that we exhibit in Section 4 are through a particular graph construction. The general idea is that, if we have a collection of graphs H 1 , . . . , H n with certain structural and labelling properties, then it is possible to combine these H i 's in some fashion to form a bigger graph G in which the H i 's retain their respective labelling properties, from which we can deduce that G itself has certain labelling properties.

In order to state this construction formally, we need to introduce some terminology first (see Figure 1 for an illustration). Let G and H be two graphs such that V (H) ⊆ V (G). We say that G contains H as a weakly induced subgraph if, for every vertex

v ∈ V (H), either d H (v) = 1 or d H (v) = d G (v). For every edge uv ∈ E(G), if u ∈ V (H) and v ∈ V (G) \ V (H), then d H (u) = 1;
we call these the border vertices of H. Also, we call the other vertices of H (i.e., those that are not border vertices) its core vertices. By definition, note that if G contains H as a weakly induced subgraph and δ(H) ≥ 2, then H is a connected component of G. In particular, if G is a connected graph, then H is isomorphic to G. For this reason, this notion makes more sense when δ(H) = 1.

Let H 1 , H 2 be two weakly induced subgraphs of a graph G. We say that H 1 and H 2 are disjoint (in G) if they share no core vertices. It follows directly from the definition that, for every Proof. Consider H j for some 1 ≤ j ≤ n. Since, by any k-labelling of a nice graph, a vertex of degree 1 cannot get the same colour as its unique neighbour, then it cannot be involved in a colouring conflict. This implies that | Hj is proper if and only if any two adjacent core vertices of H j get distinct colours by | Hj . By the definition of a weakly induced subgraph, we have d Hj (v) = d G (v) for every core vertex v of H j , which implies that c | H j (v) = c (v). Thus, for every edge uv ∈ E(H j ) joining core vertices, we have c

v ∈ V (G), if v ∈ V (H 1 ) ∩ V (H 2 ),
(u) = c | H j (u) = c | H j (v) = c (v) since is proper, meaning that
| Hj is also proper. Now, since G contains nice graphs H 1 , . . . , H n as pairwise disjoint weakly induced subgraphs, then mT(G) ≥ n i=1 mT(H i ). In the next lemma, we point out that, in some contexts, we can add some structure to a given graph without altering its value of mT. In some of the later proofs, this will be particularly convenient for applying inductive arguments or simplifying the structure of a considered graph. Lemma 3.2. Let G be a nice graph with minimum degree 1 and v ∈ V (G) be such that d G (v) = 1. If G is the graph obtained from G by adding x > 0 vertices of degree 1 adjacent to v, then mT(G ) = mT(G).

Proof. Since G contains G as a weakly induced subgraph, then by Lemma 3.1, we have that mT(G ) ≥ mT(G). To show that mT(G ) ≤ mT(G), it suffices to extend a proper 3-labelling of G to one of G that assigns label 3 to the same number of edges. To do this, simply note that since each one of the leaves adjacent to v has degree 1, its colour cannot be in conflict with that of v. Thus, the only colour conflict that can occur when extending the labelling, is between v and its unique neighbour in G. If, by labelling all of the edges incident to the leaves adjacent to v with 1s, there is a colour conflict between v and its neighbour in G, then it suffices to change exactly one of those labels to 2.

Through an easy use of Lemma 3.1, we can already establish results of interest regarding the parameter mT. For instance, we can prove that each graph class G p (p ≥ 1) contains infinitely many graphs with various properties. Observation 3.3. G p contains infinitely many graphs for every p ≥ 1.

Proof. Let H be a graph with δ(H) = 1 and mT(H) = 1 (such graphs exist, see, e.g., our results from Section 4, in particular the graphs illustrated in Figure 2). Let uv be an edge of H such that d H (u) = 1 and d H (v) ≥ 2. Also, let T be any locally irregular graph1 with an edge u v such that d T (u ) = 1 and d T (v ) ≥ 3p + 3.

Now, let G be the graph that is the disjoint union of T and of p copies H 1 , . . . , H p of H, and identify u and the p copies of u to a single vertex w. Clearly, G contains T and the disjoint union of p copies of H as pairwise disjoint weakly induced subgraphs (with a slight abuse of notations, for simplicity we refer to both the original T and its copy in G as T ). By Lemma 3.1, we have mT(G) ≥ mT(T ) + p • mT(H) = p since T is locally irregular (thus, mT(T ) = 0) and mT(H) = 1.

To prove that the equality actually holds, it suffices to construct a proper 3-labelling of G with nb (3) = p. Let be a proper 3-labelling of H such that nb (3) = 1, which exists since mT(H) = 1. To obtain , for each H i , we set (e) = (e) for every edge e of H i , while we set (e) = j for every edge e of T , where j ∈ {1, 2} is chosen so that c (w) = c (v) for v in each copy of H i (recall that c (v) is the same for each copy of H i ). As a result, for any H i , for every vertex x = w of H i , we get c (x) = c (x). Hence, for any H i , for every edge xy of H i not containing w, we have c (x) = c (y). Furthermore, for every vertex x of T different from w, we have either c

(x) = d G (x) or c (x) = 2d G (x)
, meaning that, for every edge xy of T not containing w, we have c (x) = c (y) since T is locally irregular. Now, by the construction of , note that w cannot be in conflict with its neighbours in the H i 's (due to the choice of j), and c (w

) < 3p + 3 ≤ d G (v ) ≤ c (v )
, meaning that w and v cannot be in conflict. Thus, is proper.

Note that, in the proof above, the structure of T does not matter, and can be anything as long as T is locally irregular and has the particular edge u v . In particular, T can potentially contain any graph as an induced subgraph. Thus, each graph class G p (p ≥ 1) contains infinitely many graphs with various properties.

Using similar ideas, we can actually prove that deciding if a graph G belongs to G p cannot be done in polynomial time, unless P=NP. Theorem 3.4. Given a graph G and any (fixed

) integer p ≥ 1, deciding if G ∈ G ≤p is NP-complete.
Proof. The problem is obviously in NP. Let us focus on proving it is also NP-hard. This is done by a reduction from the 2-Labelling problem, which was proved to be NP-hard, e.g., by Dudek and Wajc in [START_REF] Dudek | On the complexity of vertex-coloring edge-weightings[END_REF]. In that problem, a graph H is given, and the goal is to decide whether H admits proper 2-labellings. Given an instance H of 2-Labelling, we construct, in polynomial time, a graph G such that mT(G) = p if and only if H admits proper 2-labellings.

Looking closely at the proof from [START_REF] Dudek | On the complexity of vertex-coloring edge-weightings[END_REF], it can be noted that 2-Labelling remains NP-hard when restricted to graphs with minimum degree 1. Thus, we can assume H has this property.

The construction of G is achieved as follows. Let H be a graph with δ(H ) = 1 and mT(H ) = 1 (as mentioned in the proof of Observation 3.3, such graphs exist, and two are illustrated in Figure 2). Let uv be an edge of H such that d H (u) = 1 and d H (v) ≥ 2. Now, start from G being the disjoint union of H and of p copies H 1 , . . . , H p of H , and then identify a vertex of degree 1 of H and of the p copies of u to a single vertex w. Finally, attach new vertices of degree 1 to w so that the degree of w in G gets at least four times bigger than the degree of any of its neighbours. Clearly, the construction of G is achieved in polynomial time.

We now prove the equivalence between the two problems.

• Assume is a proper 3-labelling of G such that nb (3) = p. Note that G contains H and p copies of H as pairwise disjoint weakly induced subgraphs. Due to Lemma 3.1, and because mT(H ) = 1, this means that we must have nb | H i (3) = 1 for every i ∈ {1, . . . , p}, and, thus,

nb | H (3) = 0. Then, | H must be a proper 2-labelling of H.
• Assume is a proper 2-labelling of H. Since mT(H ) = 1, there exists a proper 3-labelling of H where nb (3) = 1. Now, let be the 3-labelling of G obtained by setting (e) = (e) for every e ∈ E(H), setting (e) = (e) for every e ∈ E(H i ) for each i ∈ {1, . . . , p}, and setting (e) = 1 for every remaining pending edge attached at w. By the properties of and , and by arguments similar to those used in the proof of Observation 3.3, no conflict can occur along an edge not containing w. Now, regarding w, due to its degree, it follows that c (w) must be strictly bigger than the colour of each of the neighbours of w. Thus, is a proper 3-labelling of G, and nb (3) = p.

Switching closed walks -A tool for upper bounds

Due to Theorem 2.1, investigating the parameters mT and ρ 3 only makes sense for graphs with chromatic number at least 3, i.e., that are not bipartite. These graphs have odd-length cycles. We take advantage of these cycles to prove the following upper bound on ρ 3 for 3-chromatic graphs.

Theorem 3.5. If G is a connected 3-chromatic graph, then ρ 3 (G) ≤ |V (G)|/|E(G)|.
Proof. Since G is not bipartite, there exists an odd-length cycle C in G. Let H be a subgraph of G constructed as follows. Start from C = H. Then, until V (H) = V (G), repeatedly choose a vertex v ∈ V (G) \ V (H) such that there exists a vertex u ∈ V (H) with uv ∈ E(G), and add the edge uv to H. In the end, H is a connected spanning subgraph of G containing only one cycle, C, which is of odd length. Then, we have

|E(H)| = |V (G)|. Let φ : V (G) → {0, 1, 2} be a proper 3-vertex-colouring of G.
In what follows, our goal is to construct a 3-labelling of G such that c (v) ≡ φ(v) mod 3 for every vertex v ∈ V (G), thus making proper. Additionally, to prove the full statement, we want to satisfy nb (3) ≤ |V (G)|/|E(G)|. Note that, aiming at vertex colours modulo 3, we can instead assume that assigns labels 0, 1, 2, and require nb (0

) ≤ |V (G)|/|E(G)|.
To obtain such a labelling, we start from assigning label 2 to all edges of G. We then modify iteratively until all vertex colours are as desired modulo 3.

As long as G has a vertex v with c (v) ≡ φ(v) mod 3, we apply the following procedure. Choose W = (v, v 1 , . . . , v n , v), a closed walk2 of odd length in G starting and ending at v, and going through edges of H only. This walk is sure to exist. Indeed, consider, in H, a (possibly empty) path P from v to the closest vertex u of C (if v lies on C, then u = v and P has no edge). Then, the closed walk vP uCuP v is a possible W . We then follow the consecutive edges of W , starting from v and ending at v, and, going along, we apply +2, -2, +2, -2, . . . , +2 (modulo 3) to the labels assigned by to the traversed edges. As a result, note that c (x) is not altered modulo 3 for every vertex x = v, while c (v) is incremented by 1 modulo 3. If c (v) ≡ φ(v) mod 3, then we are done with v. Otherwise, we repeat this switching procedure once again, so that v fulfils that property.

Eventually, we get c (v) ≡ φ(v) mod 3 for every v ∈ V (G), meaning that is proper. Recall that we have (e) = 2 for every e ∈ E(G) \ E(H). Thus, only the edges of H can be assigned label 0 by . Since |E(H)| = |V (G)| and we can replace all assigned 0s with 3s without breaking the modulo 3 property, we have mT

(G) ≤ |V (G)|, which implies that ρ 3 (G) ≤ |V (G)|/|E(G)|.
Theorem 3.5, by itself, has implications on Conjecture 2.2. In particular, every sufficiently dense connected 3-chromatic graph verifies the conjecture. This remark applies to, e.g., every connected 3-chromatic graph G with δ(G) ≥ 6, since it obviously verifies |E(G)| ≥ 3|V (G)|. Note that, in that case, the connectivity condition can actually be dropped, as every connected component of a 3-chromatic graph is 3-colourable (so, for each component, one of Theorems 2.1 and 3.5 applies).

Corollary 3.6. If G is a 3-chromatic graph with δ(G) ≥ 6, then ρ 3 (G) ≤ 1/3.
In general, and more particularly for less dense graphs, it would be interesting to find ways to improve the arguments in the proof of Theorem 3.5 to further reduce the number of assigned 3s. Note that several of our arguments could actually be subject to improvement. For instance, in the current proof, we always set (e) = 2 for an edge e ∈ E(G) \ E(H), which might be one of the reasons why many 3s might appear through the eventual walk-switching procedure. It seems, however, that in general, this is tough to improve upon significantly without further assumptions on G. Similarly, in some contexts, it might be possible to choose the unicyclic subgraph H in a clever way, but this seems hard to do in general. A more interesting direction is about choosing the proper 3-vertex-colouring φ in a more clever way. In the next lemma, we show a way to play with φ in order to reduce the number of 3s assigned by to certain sets of edges. Lemma 3.7. Let G be a graph and let be a proper {0, 1, 2}-labelling of G such that c (u) ≡ c (v) mod 3 for every edge uv ∈ E(G). If H is a (not necessarily connected) spanning d-regular subgraph of G for some d ≥ 1, then there exists a proper {0, 1, 2}-labelling of G such that c (u) ≡ c (v) mod 3 for every edge uv ∈ E(G) and that assigns label 0 to at most a third of the edges of E(H). Moreover, for every edge e ∈ E(G) \ E(H), (e) = (e).

Proof. We construct the following new labelling: starting from , add 1 (modulo 3) to all the labels assigned by to the edges of H. The resulting labelling 1 is a proper {0, 1, 2}-labelling of G such that c 1 (u) ≡ c 1 (v) mod 3 for every edge uv ∈ E(G). Indeed, for every v ∈ V (G), we have c 1 (v) ≡ c (v) + d mod 3. Thus, if there exist two adjacent vertices u, v ∈ V (G) such that c 1 (u) ≡ c 1 (v) mod 3, then c (u) ≡ c (v) mod 3, a contradiction. We define 2 in a similar fashion, by adding 1 (modulo 3) to all the labels assigned by 1 to the edges of H. Similarly, 2 is proper. Note that, for every edge e ∈ E(H), we have { (e), 1 (e), 2 (e)} = {0, 1, 2}. This implies that at least one of , 1 , 2 assigns label 0 to at most a third of the edges of E(H). Finally, since none of the labels of the edges of E(G) \ E(H) were changed to obtain 1 from and to obtain 2 from 1 , the last statement of the lemma holds.

In Lemma 3.7, if d = 2, then H forms a cycle cover of G. Thus, when H is also a unicyclic spanning connected subgraph of G, a particular application of Lemma 3.7 in conjunction with the proof of Theorem 3.5 gives the following corollary:

Corollary 3.8. If G is a 3-chromatic Hamiltonian graph of odd order, then ρ 3 (G) ≤ 1/3.
Another application of Lemma 3.7 is for d = 1, i.e., H forms an independent edge cover. That is, Lemma 3.7 in conjunction with the proof of Theorem 3.5 can be used, for instance, to prove that class-1 cubic graphs (i.e., admitting three disjoint perfect matchings) verify Conjecture 2.2. Indeed, let G be a class-1 cubic graph, and let M 1 , M 2 , M 3 be three disjoint perfect matchings of G. We can assume that G is not bipartite, as otherwise Theorem 2.1 would apply, and also that G is not K 4 (as it can be checked by hand that mT(K 4 ) = 1). Thus, G is 3-chromatic. Mimicking the proof of Theorem 3.5, we can use an odd-length cycle of G to deduce a {0, 1, 2}-labelling of G where c (u) ≡ c (v) mod 3 for every uv ∈ E(G), and, by Lemma 3.7, we can assume that, for every M i , at most a third of its edges are assigned label 0 by . Since the M i 's partition E(G), turning all 0s by into 3s, we end up with a proper 3-labelling of G where at most a third of the edges are assigned label 3. In Section 4, via a different approach, we will actually prove Conjecture 2.2 for all cubic graphs.

Regarding the proof of Theorem 3.5 and the previous arguments, it would be interesting if we could always choose the unicyclic subgraph H in such a way that it admits several disjoint perfect matchings, so that Lemma 3.7 can be employed to reduce the number of assigned 3s. In the proof of Theorem 4.20, we will point out one graph class where this strategy can be employed. 4 Results on the parameters mT and ρ 3 for some graph classes

We now use the tools introduced in Section 3 to exhibit results on the parameters mT and ρ 3 for some particular classes of 3-chromatic graphs (and beyond sometimes). In particular, we prove that, for many classes F of 3-chromatic graphs, there is no p ≥ 1 such that F ⊂ G ≤p (i.e., a constant number p of 3s is not sufficient to construct a proper 3-labelling of at least one of the graphs in F). In such cases, we provide upper bounds for ρ 3 (F).

Connected graphs needing lots of 3s

As mentioned earlier, we are aware of only two connected graphs for which the parameter ρ 3 is exactly 1/3, and these are C 3 and C 6 3 . A natural question to ask, is whether the bound in Conjecture 2.2 is accurate in general, i.e., whether it can be attained by arbitrarily large graphs.

In light of these thoughts, our goal in this subsection is to provide a class of arbitrarily large connected graphs achieving the largest possible ratio ρ 3 . Our arguments are based on our notion of weakly induced subgraphs, introduced in Section 3. Basically, the idea is to have a connected graph H with mT(H) ≥ 1, and to combine p copies H 1 , . . . , H p of H to a single connected graph G so that mT(G) ≥ p. To guarantee that ρ 3 (G) is large, the main ideas are 1) to choose H so that |E(H)| is as small as possible, and 2) to construct G so that only a few edges join the p copies of H. These two conditions ensure that |E(G)| itself is as small as possible.

We ran computer programs to find graphs H with δ(H) = 1, mT(H) ≥ 1, and with the fewest edges possible. It turns out that the smallest such graphs have 10 edges. Two such graphs, which we call A 1 and A 2 , are depicted in Figure 2. It is worth emphasising that these two graphs will be used throughout the rest of this paper, and thus, the reader should keep in mind that any later mentioning of A 1 (A 2 , respectively) refers to the graph A 1 (A 2 , respectively) in Figure 2. These two graphs will allow us to prove several lower bounds on ρ 3 for various graph classes, so, let us formally establish that they do have the desired property. Proof. A proper 3-labelling of A 1 with nb (3) = 1 is depicted in Figure 2(a), which shows that mT(A 1 ) ≤ 1. We now prove that mT(A 1 ) > 0, i.e., that there is no proper 2-labelling of A 1 . Towards a contradiction, assume a proper 2-labelling of A 1 exists.

By Observation 2.3, we have (v 6 v 7 ) = (v 6 v 8 ). Also, since is a 2-labelling, we have c (v 5 ) ∈ {3, 4, 5, 6}. We distinguish the following cases: 3 Any disjoint union of C 3 's and C 6 's reaches that value. This is why Conjecture 2.2 focuses on connected graphs.

• Case 1: c (v 5 ) = 3. Then, (v 3 v 5 ) = (v 4 v 5 ) = (v 5 v 6 ) = 1,
Assume, w.l.o.g, that c (v 3 ) = 3 and c (v 4 ) = 5. Since c (v 3 ) = 3, we have that (v 2 v 3 ) = (v 3 v 4 ) = 1, and thus, c (v 4 ) ≤ 4, a contradiction. Second, assume that (v

5 v 6 ) = 1. Since { (v 6 v 7 ), (v 6 v 8 )} = {1, 2}, we have c (v 6 ) = 4 = c (v 5 ), a contradiction.
For the next two cases, let A 1 = A 1 -{v 7 v 8 } and observe that A 1 is quasi 3-regular.

• Let us prove now that mT(A 2 ) > 0, i.e., that there is no proper 2-labelling of A 2 . Towards a contradiction, assume a proper 2-labelling of A 2 exists.

Since is a 2-labelling, we have c (v 3 ) ∈ {3, 4, 5, 6}. We distinguish the following cases: • Case 3: c (v 3 ) = 5. Then, by Observation 2.5, the 2-labelling = sw( , σ 1↔2 ) is also proper (note that A 2 is quasi 3-regular). Since c (v 3 ) = 4, we get a contradiction to Case 2 above.

• Case 1: c (v 3 ) = 3. Then, (v 2 v 3 ) = (v 3 v 4 ) = (v 3 v 5 ) = 1,
• Case 4: c (v 3 ) = 6. Then, by Observation 2.5, the 2-labelling = sw( , σ 1↔2 ) is also proper. Since c (v 3 ) = 3, we get a contradiction to Case 1 above.

Through the next constructions, A 1 and A 2 (and any other graph with convenient properties) can be used to build arbitrarily large connected graphs with large ρ 3 and particular properties. Let G be a graph. Given a graph H with at least two distinct vertices of degree 1, we define H-augmenting an edge uv of G by the following operations:

1. deleting uv from G;

2. adding a copy of H to G; 3. identifying u and any degree-1 vertex of H, and identifying v and any other degree-1 vertex of H.

Analogously, assuming H has at least one vertex of degree 1, by H-attaching a pending edge uv of G, where v has degree 1, we mean the following:

1. deleting v from G;
2. adding a copy of H to G;

identifying u and any degree-1 vertex of H.

The next lemma illustrates how we can use these two operations:

u 0,1 v 0 v 1 v 2 u 1,1 u 1,2 u 1,3 u 2,1 u 2,2 u 2,3 C 3 B 1 B 2 (a) S 3 .
. .

v 0 v 1 v 2 v g-1 u 0,1 u 1,1 u 2,1 u g-1,1 u 2,2 u 2,g B 1 B 2 B g-1 C g u 1,2 u 1,g . . . . . . . . . u g-1,g u g-1,2 (b) Sg

Bounds for connected planar graphs with large girth

Recall that the girth g(G) of a graph G is the length of its shortest cycle. For any g ≥ 3, we denote by P g the class of planar graphs with girth at least g. Note, for instance, that P 3 is the class of all planar graphs, and that P 4 is the class of all triangle-free planar graphs. Recall that the girth of a tree is set to ∞, since it has no cycle.

To date, it is still unknown whether planar graphs verify the 1-2-3 Conjecture, which makes the study of the parameters mT and ρ 3 adventurous for this class of graphs. Something we can state, however, is that there is no p ≥ 1 such that planar graphs lie in G ≤p . Indeed, since the graphs A 1 and A 2 are planar, this can be established by the construction in the proof of Theorem 4.4 (or from that of Theorem 4.5 to additionally get a cubic graph assumption), by performing it from planar starting graphs. To go further, we can consider planar graphs with large girth. Indeed, as established by Grötzsch's Theorem [START_REF] Grötzsch | Zur Theorie der diskreten Gebilde. VII. Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel[END_REF], triangle-free planar graphs are 3-colourable, which means that they verify the 1-2-3 Conjecture (see [START_REF] Karoński | Edge weights and vertex colours[END_REF]). In what follows, we prove two main results. First, we prove that, for every g ≥ 3, there is no p ≥ 1 such that P g ⊂ G ≤p . Second, we prove that, as the girth g(G) of a planar graph G grows, the ratio ρ 3 (G) decreases. As a side result, we prove Conjecture 2.2 for planar graphs with girth at least 36.

In order to prove the first result above, note that we cannot use the graphs A 1 and A 2 introduced previously, as they contain triangles. Instead, we provide another construction, yielding, for any g ≥ 3, a planar graph S g with girth g. Start from S g being the cycle C g = (v 0 , . . . , v g-1 , v 0 ) on g vertices. Then, for each i ∈ {0, . . . , g -1}, add a new vertex u i,1 and the edge v i u i,1 to S g . Then, for every i ∈ {1, . . . , g -1}, add a cycle B i = (u i,1 , u i,2 , . . . , u i,g , u i,1 ) to S g , where u i,2 , . . . , u i,g are new vertices. Finally, let u 0,1 be the root of S g . See Figure 3 for an illustration of S 3 and S g . It is clear that all the cycles of S g have length g, and thus, g(S g ) = g. Moreover, S g is clearly planar, and |E(S g )| = g 2 + g.

Note that S g is bipartite whenever g is even. Since δ(S g ) = 1, in such cases we have mT(S g ) = 0 by Theorem 2.1. When g ≡ 1 mod 4, it can be checked (for instance, by using some of the arguments in the proof of the upcoming Lemma 4.8) that S g admits proper 2-labellings, and thus, we have mT(S g ) = 0 in those cases as well. The main point for considering this construction is for the last possible values of g, the values where g ≡ 3 mod 4, for which the following is verified: Lemma 4.8. For every g ≥ 3 with g ≡ 3 mod 4, we have mT(S g ) = 1.

Proof. We begin by showing that a proper 2-labelling of S g must have specific properties. In what follows, for every i ∈ {1, . . . , g -1}, we denote by H i the subgraph of S g induced by V (B i ) ∪ {v i }. Claim 4.9. Let i ∈ {1, . . . , g -1}. By any proper 2-labelling of H i , we have (u i,1 u i,2 ) = (u i,g u i,1 ), and thus, c (u i,1 ) = (u i,1 v i ) + 3. Furthermore, such a proper 2-labelling exists.

Proof of the claim. The first part of the claim follows from Observation 2.3. Indeed, since g ≡ 3 mod 4, it follows that we must have (u i,1 u i,2 ) = (u i,3 u i,4 ) = • • • = (u i,g u i,1 ). Now, it is easy to check that the following is a proper 2-labelling of H i . Start by setting (u i,1 u i,2 ) = 2. Then, continue from u i,2 u i,3 and, following the edges of B i until reaching u i,g u i,1 , assign labels 1, 1, 2, 2, 1, 1, 2, . . . , 2, 1, 1, 2, 2, 1, 1. The edge u i,1 v i can then be assigned any label in {1, 2}.

Assume that there exists a proper 2-labelling of S g , and let {α, β} be a permutation of {1, 2}. We define the set J = {j ∈ {0, . . . , g -1} :

(v j-1 v j ) = (v j v j+1 )},
where, here and in what follows, indices are taken modulo g. Observe that |J| ≡ 0 mod 2 and that J = ∅. Indeed, assume that J = ∅. Then, we would have that all the edges of C g receive the same label α or β. Since is proper, it must be that

(v i u i,1 ) = (v i+1 u i+1,1 ) for all 0 ≤ i ≤ g -1.
This is a contradiction since g is odd and is a 2-labelling. Let j ∈ J such that j ≥ 1 (the vertex v j exists since |J| ≡ 0 mod 2 and J = ∅). We have that (v j-1 v j ) = (v j v j+1 ), which implies that (v j-1 v j ) + (v j v j+1 ) = 3. It follows that c (v j ) = (v j u j,1 ) + 3. Note now that the labelling j = | Hj is a proper 2-labelling of H j (since d Hj (v j ) = 1). Therefore, by Claim 4.9, it follows that c (u j,1 ) = c j (u j,1 ) = j (u j,1 v j ) + 3 = (u j,1 v j ) + 3 = c (v j ), a contradiction. So far, we have proved that mT(S g ) ≥ 1. In order to show that mT(S g ) = 1, it suffices to provide a proper 3-labelling of S g such that nb (3) = 1. We construct one such labelling as follows. For every i ∈ {1, . . . , g -1}, we label the subgraph B i following the 2-labelling scheme provided in Claim 4.9. Then, we set (v 0 v 1 ) = 3 and, for every edge e ∈ E(C g ) \ {v 0 v 1 }, we set (e) = 1. Finally, for the edges of the form

v i u i,1 (0 ≤ i ≤ g -1), we set (v 0 u 0,1 ) = 1, (v 1 u 1,1 ) = 2, (v 2 u 2,1 ) = 1, . . . , (v g-2 u g-2,1 ) = 2, (v g-1 u g-1,1 ) = 1. It is clear that c (v 0 ) = 5
, and c (v 1 ) = 6, while the colours of the vertices of the rest of the cycle C g alternate between 3 and 4. Moreover, for all

2 ≤ i ≤ g -1, if c (v i ) = 3, then c (u i,1 ) = 4
, and if c (v i ) = 4, then c (u i,1 ) = 5 (by Claim 4.9). Thus, is a proper 3-labelling that assigns label 3 to only one edge of S g .

We are now ready to prove our lower bound.

Theorem 4.10. For every g ≥ 3, there exist arbitrarily large connected planar graphs G with g(G) ≥ g and ρ 3 (G) ≥ 1 g 2 +g , where g is the smallest natural number such that g ≥ g and g ≡ 3 mod 4.

Proof. For any integer p ≥ 1, denote by G the graph obtained from p disjoint copies H 1 , . . . , H p of S g by identifying their roots to a single vertex. Clearly, G is planar and has girth g ≥ g . Furthermore, G clearly contains p copies of S g as pairwise disjoint weakly induced subgraphs. Then, Lemma 3.1 implies that mT(G) ≥ p • mT(S g ), and p • mT(S g ) = p by Lemma 4.8. Since G has p|E(S g )| = p(g 2 + g) edges, the result follows. Moreover, these arguments apply for any value of p, and so, G can be as large as desired.

It is not too complicated to check that our construction in the proof of Theorem 4.10 yields planar graphs G of girth g satisfying mT(G) = |E(G)|/(g 2 + g) (when g ≡ 3 mod 4), which implies that the lower bound in the statement is somewhat tight here. Note also that the graph G constructed in the proof of Theorem 4.10 does not have girth g when g ≡ 3 mod 4. In this case, to obtain a similar result for a graph of girth g , we can additionally identify a single vertex of a new cycle of length g to the same single vertex as the roots of the p copies of S g in the previous proof.

We now proceed to prove that ρ 3 (G) ≤ 2 k-1 for any nice planar graph G of girth g ≥ 5k + 1, when k ≥ 7. In other words, the bigger the girth of a planar graph G, the smaller ρ 3 (G) gets.

The following theorem from [START_REF] Chang | On the precise value of the strong chromatic index of a planar graph with a large girth[END_REF] is one of the main tools we use to prove this result. Recall that, for any k ≥ 1, a k-thread in a graph G is a path (u 1 , . . . , u k+2 ), where the k inner vertices u 2 , . . . , u k+1 all have degree 2 in G. Theorem 4.11 (Chang,Duh [9]). For any integer k ≥ 1, every planar graph with minimum degree at least 2 and girth at least 5k + 1 contains a k-thread.

We can now proceed with the main theorem. Theorem 4.12. Let k ≥ 7. If G is a nice planar graph with g(G) ≥ 5k + 1, then ρ 3 (G) ≤ 2 k-1 . Proof. Throughout this proof, we set g = g(G). The proof is by induction on the order of G. The base case is when |V (G)| = 3. In that case, G must be a path of length 2 (due to the girth assumption), and the claim is clearly true. So let us focus on proving the general case.

We can assume that G is connected. If G is a tree, then χ Σ (G) ≤ 2 and we have ρ 3 (G) = 0. So, from now on, we may assume that G is not a tree. We can also assume that G has no vertex v to which is attached a pending tree T v that is not a star with center v. Indeed, if such a T v exists, then we can find a vertex u ∈ V (T v ) \ {v} whose all neighbours u 1 , . . . , u x but one are degree-1 vertices. Since G is not a tree, the graph G = G -{u 1 , . . . , u x } is clearly a nice planar graph with girth g, admitting, by the inductive hypothesis, a proper 3-labelling attesting that ρ 3 (G ) ≤ 2 k-1 . Lemma 3.2 tells us that such a labelling can be extended to one of G.

Let G -be the graph obtained from G by removing all vertices of degree 1. Note that removing vertices of degree 1 from G can neither decrease its girth nor result in a tree. Since G has girth g ≥ 5k + 1 and does not contain any cut vertex v ∈ V (G) as described above, the graph G - has minimum degree 2. By Theorem 4.11, G -contains a k-thread P . Let u 1 , . . . , u k+2 be the vertices of P , where d G -(u i ) = 2 for all 2 ≤ i ≤ k + 1. Thus, the vertices of P exist in G except that each of the vertices u i (for 2 ≤ i ≤ k + 1) may be adjacent to some vertices of degree 1 in addition to their adjacencies in G -. Let G be the graph obtained from G by removing the vertices u 3 , . . . , u k and all of their neighbours that have degree 1 in G. Note that G might contain up to two connected components. In case G has exactly two connected components, then, due to a previous assumption, none of these can be a tree, which implies that G is nice. If G is connected, then, because it has at least two edges (u 1 u 2 and u k+1 u k+2 ), it must be nice. Furthermore, in both cases, the girth of G is at least that of G. Then, by combining the inductive hypothesis and the fact that ρ 3 (T ) = 0 for every nice tree T , we deduce that

ρ 3 (G ) ≤ 2 k-1 . To obtain a proper 3-labelling of G such that ρ 3 (G) ≤ 2 k-1 , we extend a proper 3-labelling of G corresponding to ρ 3 (G ) ≤ 2
k-1 , as follows. First, for each edge incident to a vertex of degree 1 that we have removed, label it with 1. Note that none of these vertices of degree 1 can, later on, be in conflict with their neighbour since they have degree 1. Now, for each 2 ≤ j ≤ k -2, in increasing order of j, label the edge u j u j+1 with 1 or 2, so that the resulting colour of u j does not conflict with the colour of u j-1 . Finally, label the edges u k-1 u k and u k u k+1 with 1, 2 or 3, so that the resulting colour of u k-1 does not conflict with that of u k-2 , the resulting colour of u k does not conflict with that of u k-1 nor with that of u k+1 , and the resulting colour of u k+1 does not conflict with that of u k+2 . Indeed, this is possible since there exist at least two distinct labels {α, β} ({α , β }, respectively) in {1, 2, 3} for u k-1 u k (u k u k+1 , respectively) such that the colour of u k-1 (u k+1 , respectively) is not in conflict with that of u k-2 (u k+2 , respectively). Thus, w.l.o.g., choose α and α for the labels of u k-1 u k and u k u k+1 , respectively. If the colour of u k does not conflict with that of u k-1 nor with that of u k+1 , then we are done. If the colour of u k conflicts with both that of u k-1 and that of u k+1 , then it suffices to change both the labels of u k-1 u k and u k u k+1 to β and β , respectively. Lastly, w.l.o.g., if the colour of u k only conflicts with that of u k-1 , then it suffices to change the label of u k u k+1 to β . The resulting labelling of G is thus proper. Moreover, |E(G) \ E(G )| ≥ k -1 and assigns label 3 to at most two more edges than , and so, the result follows.

Bounds for connected cacti

Recall that a cactus is a graph in which every edge is contained in at most one simple cycle. Note that trees are also cacti since they do not contain cycles.

First off, note that the graphs S g introduced in Section 4.3, and those we have constructed from them in the proof of Theorem 4.10, are all cacti (all of their cycles are actually disjoint). Since the smallest graph S g is S 3 , which has 12 edges, the proof of that theorem implies the following. Theorem 4.13. There exist arbitrarily large connected cacti G with ρ 3 (G) ≥ 1/12.

We now focus on the upper bound. We actually end up proving Conjecture 2.2 for cacti. Proof. The proof is done by induction on |V (G)|. Since the claim is clearly true when G has only three vertices, let us consider the general case. Clearly, we can assume that G is connected (as otherwise we could use the inductive hypothesis on each connected component), is not a tree (since mT(T ) = 0 for every nice tree T ), is not bipartite (by Theorem 2.1), and is not a cycle (see [START_REF] Bensmail | On proper labellings of graphs with minimum label sum[END_REF]). Throughout this proof, for readability reasons, we say that a proper 3-labelling is good if it assigns label 3 to at most a third of the edges of the labelled graph. We first prove that if G has some specific properties, then we can remove some vertices from G, resulting in a nice cactus G that is smaller than G, and extend a good labelling of G , obtained by induction, into a good labelling of G, thus proving the statement for G. It can then be assumed that G does not have these properties, which will simplify its structure and allow us to prove the final inductive step.

B 1 B 5 B 4 B 7 B 2 B 3 B 6 (b) The cactus G - b B1 c v1 b B2 c v2 b B3 c v3 b B5 b B4 c v4 b B6 c v5 b B7 (
Let us state a few more remarks. Let be an extension of that assigns labels from {1, 2} to the edges of G that are not in G . If this is proper, then note that it is also good. Similarly, if assigns label 3 to at most a third of the edges of G that are not in G and is proper, then it is also good.

We start by analysing certain cycles of G. To define those cycles, let us consider the following terminology (see Figure 4 for an accompanying illustration). We denote by G -the cactus obtained from G by repeatedly deleting vertices of degree 1 until the remaining graph has minimum degree 2. Since G contains cycles, note that G -is not empty. We now consider the block graph B(G -) of G -, which is defined as follows [START_REF] Diestel | Graph Theory[END_REF]. A block of G -is a maximal 2-connected subgraph of G -. The block graph B(G -) is the tree having a block vertex b B for every block B of G -, a vertex c v for every cut vertex v of G -, and in which two vertices b B and c v are joined by an edge if and only if B contains v in G -. Note that B(G -) is not empty since G -has at least one cycle, and, due to how G -was obtained from G, note that all the leaves of B(G -) are block vertices corresponding to cycles in G -. In what follows, we study structures around end-cycles, where an end-cycle C of G refers to a cycle of G -, which corresponds to a leaf b C of B(G -). In G -, every vertex of an end-cycle C has degree 2, except for one, which we denote by r and call the root of C, while its other vertices are the inner vertices of C. Note that end-cycles are better defined as soon as G has at least two cycles. In case G has only one cycle C, then we consider C as an end-cycle, its root being any of its vertices of degree more than 2 in G (at least one exists since G is not a cycle).

In what follows, we consider any end-cycle C of G. We first investigate properties of pending trees attached to the vertices of C. For every vertex v of C, we define T v as the pending tree rooted at v in G. Note that there might be no edges in such a T v , i.e., we can have V (T v ) = {v}. We implicitly assume that every T v comes with the natural (virtual) orientation of its edges from the root (v) to the leaves. Also, we say that T v is inner if v is indeed an inner vertex of C. Claim 4.15. If some T v has edges and is not a star, then there is a good labelling of G.

Proof of the claim. Let us consider a deepest (i.e., farthest from v) vertex u of T v , where all of its x ≥ 1 children are leaves. Since T v is not a star, we have u = v. Then, the graph G obtained from G by removing all of these x leaves is a nice cactus (due to the presence of the cycle C) in which u has degree 1. Thus, G admits a good labelling by the inductive hypothesis. Lemma 3.2 tells us that this good labelling of G can be extended to one of G. Claim 4.16. If some inner T v is a star with at least two edges, then there is a good labelling of G.

Proof of the claim. Let G be the graph obtained from G by removing two leaves u, u of T v . Clearly, G is a cactus, and G is nice due to the presence of C. By the inductive hypothesis, there is a good labelling of G . To obtain one of G, it suffices to extend this labelling to vu and vu by assigning labels 1 and 2 in such a way that no colour conflict arises. Recall that, by a k-labelling of a nice graph, a vertex of degree 1 cannot be involved in a colour conflict with its neighbour. Then, it suffices to label vu and vu so that no colour conflict arises between v and its two neighbours in C. Note that there are three different ways to label edges vu and vu (assigning label 1 twice, assigning 2 twice, or assigning both 1 and 2 once). Under these labellings, the vertex v can take three different colours, while it has two neighbours in C. Hence, at least one labelling for the two edges extends the labelling of G to a good labelling of G.

Thus, in C, any inner T v can be assumed to have at most one edge. Claim 4.17. If C has length at least 4 and some inner T v has an edge, then there is a good labelling of G.

Proof of the claim. Assume C = (v 0 , v 1 , . . . , v n-1 , v 0 ), where v 0 = r is the root of C and n ≥ 4. By Claims 4.15 and 4.16, each T vi (where i ∈ {1, . . . , n -1}) has at most one edge.

Assume first that there is an i ∈ {2, . . . , n -2} such that T vi has an edge v i u. Let G be the graph obtained from G by removing u and v i . Clearly, G is a cactus with at least two edges (v 0 v 1 and v n-1 v 0 ), so it is nice. By the inductive hypothesis, there is a good labelling of G , which we want to extend to one of G. To that aim, we have to label the three edges v i u, v i v i-1 , v i v i+1 (where, here and in what follows, indices are taken modulo n) so that no colour conflict arises, and label 3 is assigned at most once. First, we assign 1 or 2 to v i v i-1 so that v i-1 does not get in conflict with v i-2 . Second, we assign 1 or 2 to v i v i+1 so that v i+1 does not get in conflict with v i+2 . Third, we assign 1, 2 or 3 to v i u so that v i gets in conflict with neither v i-1 nor v i+1 . As mentioned earlier, u cannot get in conflict with v i due to its degree, so the resulting labelling of G is good.

Assume now that T vi has no edge for every i ∈ {2, . . . , n -2}, but T v1 has an edge v 1 u (the case where T vn-1 has an edge is symmetrical). This means that each of v 2 , . . . , v n-2 has degree 2. In this case, we consider G the cactus obtained from G by removing u and v 2 . Note that G has more than one edge since r has degree at least 3 in G. Then, G is nice. By the inductive hypothesis, there is a good labelling of G . To extend it to one of G, we must label the edges v 1 u, v 1 v 2 , v 2 v 3 so that no colour conflicts arise, and label 3 is assigned at most once. Similarly as in the previous case, this can be achieved by first labelling v 2 v 3 with 1 or 2 so that no conflict between v 3 and v 4 arises, then labelling v 1 v 2 with 1 or 2 so that no conflict between v 2 and v 3 arises, and lastly labelling v 1 u with 1, 2 or 3 so that v 1 is not in conflict with v 0 nor v 2 .

5 u 4 v 3 w 2 u 2 2 1 2 (a) G is a 1-triangle 5 u 6 v 3 w 2 u 2 v 2 2 1 2 2 (b) G is a 2-triangle
Due to the previous claims, in G we can assume that C is either a cycle of any length at least 3 (i.e., all inner vertices have degree 2), or a triangle where one or two of its inner vertices have a pending edge attached (i.e., one or two of the T v 's have size 1). We call the first of these two triangle configurations a 1-triangle, while we call the second configuration a 2-triangle. For convenience, we also regard these configurations as end-cycles, though they are technically not cycles in G.

We are now ready to conclude the proof. If G has only one cycle, then, by the previous claims and our original assumption that G is not just a cycle, it must be that G is a triangle (u, v, w, u) with a pending vertex attached to u and possibly one attached to v, in which case the claim can be verified easily (Figure 5 illustrates proper 2-labellings of G for these two cases). So G has at least two cycles. From now on, let us consider two cycles C x and C 1 of G such that the block vertices b Cx and b C1 are two leaves at maximum distance d in B(G -). Note that C 1 is an end-cycle in G, and let r denote its root. Observe that there might be other (end-)cycles of G at distance d (in B(G -)) from C x , with root r. In case these cycles exist, we denote them by C 2 , . . . , C q . Then C 1 , . . . , C q are end-cycles in G with the same root r, and, by how these C i 's were chosen, r either has only one neighbour u or only two neighbours u, u of degree at least 2 that does/do not belong to the C i 's. More precisely, r is connected to the rest of the graph either via a path (through an edge ru), or via a unique cycle (containing both u and u ). Furthermore, there might be vertices of degree 1 adjacent to r. Indeed, by Claim 4.15, if there is a pending tree T r attached at r, then T r must be a star with center r. Recall that each of the C i 's is a cycle, a 1-triangle, or a 2-triangle, due to previous claims. Now, let G be the cactus obtained from G by removing all the non-root vertices of the C i 's (i.e., all their inner vertices, plus the at most two pending vertices of the 1-triangles and 2-triangles). Since G contains at least one cycle, it is nice, and thus, admits a good labelling by the inductive hypothesis. Our goal is to extend it to one of G by labelling the removed edges so that no conflict arises and at most a third of these edges are assigned label 3.

• Assume q ≥ 2. We first label the edges of every C i that is a cycle, assigning consecutive labels 2, 1, 1, 2, 2, 1, 1, . . . while going around, starting and ending with an edge incident to r. Note that this avoids any conflict between the inner vertices of C i , that their colours are at most 4, and that this increases the colour of r by at least 3. For every C i that is a 1-triangle, we assign label 2 to its two edges incident to r, and label 1 to its two other edges. Note that this raises no conflict between the inner vertices of C i , that their colours are at most 4, and that the colour of r is increased by 4. Finally, for every C i that is a 2-triangle, we assign label 2 to its two edges incident to r and to one pending edge, and label 1 to the two other edges. As a result, no conflict arises between inner vertices, their colours are at most 5, and the colour of r is increased by 4. Since q ≥ 2 and r has at least one neighbour not in the C i 's, the colour of r is at least 7, and thus, r cannot be in conflict with its neighbours in the C i 's. However, we still have to make sure that the colour of r is different from that of u (where u is the sole neighbour of r that does not belong to any of the C i 's) or of that of u and u (where u and u are the two neighbours of r that do not belong to any of the C i 's). Note that, in each C i , there is an edge labelled 2 incident to r that can be relabelled 3 without causing conflicts between the inner Figure 6: A good labelling as described in the proof of Theorem 4.14 in the case where q = 1, C 1 is a 2-triangle, and, apart from v 1 and v 2 , the vertex r has two neighbours u and u . The underlined labels and colours correspond to the labelling provided from the inductive hypothesis (and thus, must not be modified). Now, assuming that the underlined labels and colours are as shown in the figure, we must have c (r) = 4, as otherwise r would be in a colour conflict with either u or u . Thus, it must be that (rv 1 ) = (rv 2 ) = 1. Then, we get that (v 1 u 1 ) = 1 and (v 2 u 2 ) = 3.

vertices. Indeed, if C i is a cycle, then the very first labelled edge is such an edge. If C i is a 1-triangle or 2-triangle, then the one of its two edges labelled 2 incident to r going to the inner vertex with the largest colour, is such an edge. Thus, by changing the label from 2 to 3, of one or two of these edges, we can increment the colour of r by 1 or 2 to avoid the colours of u and u (if it exists). This means that, by introducing at most two 3s, we can get a proper 3-labelling of G, which is good since q ≥ 2.

• Assume q = 1. Assume first that C 1 is a 1-triangle or a 2-triangle. Let (r, v 1 , v 2 , r) denote the vertices of the cycle of C 1 , and u 1 and u 2 (if it exists) denote the pending vertices attached to v 1 and v 2 , respectively. We first label rv 1 and rv 2 with 1 or 2 so that no conflict arises between r and its neighbours u and u (if it exists). This is possible since there are three possible combinations. In the case where C 1 is a 1-triangle, then we label v 1 v 2 with 1 or 2 so that no conflict arises between v 2 and r. In the case where C 1 is a 2-triangle, then we label v 1 v 2 with 1. Now, if C 1 is a 1-triangle, then we label v 1 u 1 with 1, 2 or 3 so that no conflict arises between v 1 and r nor between v 1 and v 2 . If C 1 is a 2-triangle, then we label v 1 u 1 with 1 or 2 so that no conflict arises between v 1 and r, and then we label v 2 u 2 with 1, 2 or 3 so that no conflict arises between v 2 and r nor between v 1 and v 2 . In all cases, we assign label 3 to at most one edge, so the resulting proper 3-labelling of G is good since no conflict arises. Figure 6 illustrates a possible good labelling for the case where C 1 is a 2-triangle and both u and u exist. Assume now that C 1 is a cycle. First, assume that u exists. We consider the edges of C 1 , and assign to them labels 1 and 2 as previously, i.e., by applying the labelling pattern 2, 1, 1, 2, 2, 1, 1, . . . from one edge incident to r to the other. We consider two cases:

-Assume first that, in the labelling of C 1 , the two edges incident to r get assigned distinct labels (1 and 2). As earlier, no two inner vertices of C 1 are in conflict, their colours are at most 4, and, since u exists, the colour of r is at least 5. If this raises no conflict between r and its neighbours u or u , then we are done. Otherwise, note that turning the label assigned to any of the two edges of C 1 incident to r into a 3, raises no conflict between two vertices of C 1 . Since these two edges are labelled differently, one with label 1 and the other with label 2, this means that by introducing label 3 once in C 1 , we can increment the colour of r by 1 or 2 so that we avoid any conflict between r and its neighbours u and u . Then, we can deduce a good labelling of G. -Assume now that both edges incident to r in C 1 get assigned label 2. Then, this time, the colour of r is at least 6. If there is no conflict between r and one of its neighbours u and u , then we are done. So, we can assume there is a conflict, and also that changing the label of one of the two edges of C 1 incident to r to 3, makes r in conflict with the second one of these two vertices. Then, note that we get a good labelling when labelling C 1 following the pattern 1, 2, 2, 1, 1, 2, 2, . . . instead, since r gets its two incident edges in C 1 being assigned label 1, the colour of r is at least 4 and smaller than the previous colours we have produced for r, and the colours of the two neighbours of r in C 1 are at most 3. All conditions are now met to invoke the arguments in the proof of Theorem 3.5, from which we can deduce a proper {0, 1, 2}-labelling of G where adjacent vertices get distinct colours modulo 3, and in which only the edges of (our) H are possibly assigned label 0. Let us now consider the subgraph H of G obtained from H by adding the edge v 0 v 1 , which is present in G. Recall that (v 0 v 1 ) = 2 by default. Note that H contains at least two disjoint perfect matchings

M 1 , M 2 . Indeed, since |V (G)| is even, a first perfect matching M 1 of H contains v 0 v 1 , v 2 v 3 , . . . , v n-2 v n-1 . A second perfect matching M 2 of H contains v 1 v 2 , v 3 v 4 , .
. . , v n-1 v 0 . By Lemma 3.7, we can assume that at most a third of the edges in M 1 ∪ M 2 are assigned label 0 by . Since

|M 1 | + |M 2 | = |E(H )| -1 = |E(H)|, but the edge v 1 v x ∈ E(H) is not included in M 1 nor M 2 (and so may have label 0 too), this gives nb (0) ≤ E(H) 3 + 1, which is less than |E(G)|/3 since |E(G)| ≥ |V (G)| + 3. More formally, nb (0) ≤ |E(H)| 3 + 1 = |V (G)| 3 + 1 ≤ |E(G)| -3 3 + 1 = |E(G)| 3 .
By turning 0s by into 3s, we get a proper 3-labelling of G with the same upper bound on the number of assigned 3s.

Theorem 4.19 does not cover all 2-connected outerplanar graphs. However, it covers all such graphs with at least three chords. Thus, to get a generalisation of Theorem 4.19 for all 2-connected outerplanar graphs, one has to prove a similar result for the 3-chromatic ones with at most two chords. Those with no chords are exactly odd-length cycles, for which the claim holds (see, e.g., [START_REF] Bensmail | On proper labellings of graphs with minimum label sum[END_REF]). For those with one or two chords, the claim can also be verified, for instance through considering all of the possible ways for the (at most two) chords to interact in such a 2-connected outerplanar graph, and, for each possible configuration, extending a proper 3-labelling from face to face. Let us mention that the number of cases to consider can be reduced drastically by applying some of the arguments used in the proof of Theorem 4.12 to deal with long threads. We voluntarily omit a tedious proof, which would be less interesting than that of Theorem 4.19 (whose main purpose is to illustrate how some of the tools from Section 3 can be used).

Halin graphs

We now proceed by proving Conjecture 2.2 for a 4-colourable family of graphs. A Halin graph is a planar graph with minimum degree 3 obtained as follows. Start from a tree T with no vertex of degree 2, and consider a planar embedding of T . Finally, add edges to form a cycle going through all the leaves of T in the clockwise order w.r.t. this embedding. A Halin graph is called a wheel if it is constructed from a tree T with diameter 2 (i.e., T is a star).

Halin graphs are known to have many properties of interest, such as having triangles, being Hamiltonian, and having Hamiltonian cycles going through any given edge (see, e.g., [START_REF] Wang | On backbone coloring of graphs[END_REF]). Also, Halin graphs are 3-degenerate, so, due to the presence of triangles, each of them has chromatic number 3 or 4. The dichotomy is well-understood, as a Halin graph has chromatic number 4 if and only if it is a wheel of even order [START_REF] Wang | List Coloring Halin Graphs[END_REF]. This allows us to use our tools from Section 3 to establish an upper bound on ρ 3 for most Halin graphs (the 3-chromatic ones), while we can treat the remaining ones separately. Proof. First, consider the case where G is a wheel of even order n. If n = 4, then G = K 4 , and the statement holds (since it can be checked by hand that ρ 3 (K 4 ) = 1/6). For n ≥ 6, we have that mT(G) = 0. Indeed, let v be the center of the star T , and let v 2 , . . . , v n be the leaves of T . We can construct a proper 2-labelling of G as follows: start from v 2 v 3 , and, following the edges of the cycle joining the leaves of T in increasing order of their indices, assign labels (see Figure 8 for an illustration of the described labelling). It is easy to check that in both cases is a proper 2-labelling of G. Thus, ρ 3 (G) = 0 and the statement holds.

1, 1, 2, 2, 1, 1, 2 . . . , until v n v 2 is labelled. If (v n v 2 ) = 1, then set (vv 2 ) = 1 and (vv i ) = 2 for every 3 ≤ i ≤ n. Otherwise, if (v n v 2 ) = 2 (and so, (v n-1 v n ) = 1), set (vv 2 ) = 2 and (vv i ) = 1 for every 3 ≤ i ≤ n
Next, consider the case where G is not a wheel of even order. Then, χ(G) = 3. If |V (G)| is odd, then the result follows from Corollary 3.8. Thus, we can assume that |V (G)| is even.

By considering any non-leaf vertex r of T in G, and defining a usual root-to-leaf (virtual) orientation, since no vertex has degree 2 in T , it can be seen that G has a triangle (u, v, w, u), where v, w are leaves in T with parent u. Furthermore,

d G (v) = d G (w) = 3, while d G (u) ≥ 3.
Due to these degree properties, note that if we consider C a Hamiltonian cycle traversing uv, then C must also include either wu or vw. More precisely, if we orient the edges of C, resulting in a spanning oriented cycle C, then, at some point, C enters (u, v, w, u) through one of its vertices, goes through another vertex of the triangle, and then through the third one, before leaving the triangle. In other words, C traverses all the vertices of (u, v, w, u) at once.

Up to relabelling the vertices of (u, v, w, u), we can assume that C enters the triangle through u, then goes to v, before going to w and leaving the triangle. Let us consider H, the subgraph of G containing the three edges of (u, v, w, u), and all successive edges traversed by C after leaving the triangle except for the edge going back to u. Note that H is a unicyclic spanning connected subgraph of G, in which the only cycle is the triangle (u, v, w, u) to which is attached a hanging path (w, x 1 , . . . , x n-3 ) containing all the other vertices of G (i.e., n = |V (G)|). Furthermore, in E(G) \ E(H), if we set x = x n-3 , then the edge xu exists. Since H is spanning, connected, and unicyclic, |E(H)| = |V (G)|, which is at most 2|E(G)|/3, since δ(G) ≥ 3.

All conditions are now met to invoke the arguments in the proof of Theorem 3.5, from which we can deduce a proper {0, 1, 2}-labelling of G where adjacent vertices get distinct colours modulo 3, and in which only the edges of the chosen H are possibly assigned label 0. Let us now consider the subgraph H of G obtained from H by adding the edge xu, which is present in G. Recall that (xu) = 2 by default. Note that H contains at least two disjoint perfect matchings M 1 , M 2 . Indeed, since |V (G)| is even, then, in H, the hanging path attached at w has odd length. A first perfect matching M 1 of H contains x n-3 x n-4 , x n-5 x n-6 , . . . , wx 1 , and uv. A second perfect matching M 2 of H contains x n-4 x n-5 , x n-6 x n-7 , . . . , x 2 x 1 , and wv and xu. Now, by Lemma 3.7, we can assume that at most a third of the edges in M 1 ∪ M 2 are assigned label 0 by . Since By turning 0s by into 3s, we get a proper 3-labelling of G with the same upper bound on the number of assigned 3s.

Conclusion

This work was dedicated to studying the importance of 3s in designing proper 3-labellings, this aspect being motivated by a presumption from previous works that proper 3-labellings of graphs, in general, should require only a few 3s. This led us to introducing the two quantifying parameters mT and ρ 3 . As a main contribution, we have introduced, in Section 3, some tools for deducing bounds on these parameters. Applications of these, in Section 4, led us to results for specific classes of 3-chromatic graphs. In particular, we have established that, for several simple classes F of graphs, there is no p ≥ 0 such that F ⊂ G ≤p . In such cases, we have provided bounds on ρ 3 (F).

Several directions for further research sound particularly appealing. A first one is to prove Conjecture 2.2 for more classes of graphs, or to exhibit weaker upper bounds towards it. Another one is to investigate whether the bound of 1/3 in that conjecture is close to being tight or not, in general. Indeed, at the moment we only know of two small connected graphs, namely C 3 and C 6 , which attain the bound, while the class of arbitrarily large graphs with the biggest value ρ 3 we could construct, achieves a ratio of 1/10 (Theorem 4.4).

An interesting perspective could be to provide better lower bounds, i.e., find graphs requiring even more 3s in their proper 3-labellings. This could be done through using Lemma 4.3 (just as in Theorem 4.4 for instance) with graphs H that are better than those used throughout this work. In particular, it would be interesting to find such graphs H with similar properties to A 1 and A 2 , but with ρ 3 (H) > 1/10. Other properties of interest for H include large density. Note that the graphs we construct, for instance, in the proof of Theorem 4.4, are rather sparse due to how H-augmentations are performed. It is not always true, however, that performing H-augmentations results in sparse graphs. For example, consider A 2 -augmenting a small number of edges of a huge complete graph. Following these thoughts, we wonder whether denser versions of A 1 and A 2 exist. Another property of interest could be high connectivity. As mentioned after the proof of Theorem 4.5, the graphs A 1 and A 2 can be used to produce 2-connected graphs. However, these graphs cannot be used to produce graphs with connectivity at least 3.

Other directions of interest include bounds that are missing in Section 4. For instance, we are missing an upper bound on ρ 3 for a few classes of 3-chromatic graphs, such as separable outerplanar graphs and, more generally, series-parallel graphs. Regarding our upper bound for Halin graphs (Theorem 4.20), the main point of interest in the proof lies in that it shows an application of Lemma 3.7. However, we were not able to come up with examples of arbitrarily large Halin graphs needing more and more 3s in their proper 3-labellings. Actually, we are aware of only three Halin graphs that do not admit proper 2-labellings. Two of them are K 4 and the prism graph (Cartesian product of K 3 and K 2 ). The third one is constructed as follows: start with two perfect binary trees on 7 vertices each and add an edge between the roots (degree-2 vertices) of these trees; from the resulting tree T , construct G as explained in Section 4.5.2. All three of these graphs turn out to lie in G 1 . Thus, though we were not able to prove it, it is possible that there exists a p ≥ 1 such that Halin graphs are in G ≤p , and even that p = 1.

Let us mention a last intriguing open question regarding complete graphs. It is known from [2] that complete graphs K n with n ≥ 5 admit equitable proper 3-labellings, which implies that they verify Conjecture 2.2, i.e., mT(K n ) ≤ |E(K n )|/3 which is roughly of order n 2 /6. In [START_REF] Bensmail | On proper labellings of graphs with minimum label sum[END_REF], the authors exhibited proper 3-labellings of complete graphs where the sum of assigned labels is as small as possible. Looking closely at the proof, it turns out that the designed proper 3-labellings assign label 3 to roughly n/4 edges, which yields a better upper bound on ρ 3 (K n ). Determining the precise ratio in general sounds like an interesting challenge. Through computer experimentation, we were able to verify that K n ∈ G 1 for 3 ≤ n ≤ 5, while K n ∈ G 2 for 6 ≤ n ≤ 9, and K n ∈ G 3 for 10 ≤ n ≤ 12. However, we did not manage to prove a general result. We are not even sure if there exists a p ≥ 3 such that all complete graphs are in G ≤p .

Figure 1 :

 1 Figure1: A graph G containing another graph H as a weakly induced subgraph. In G, the white vertices can have arbitrarily many neighbours in the grey part, while the full neighbourhoods of the black vertices are as displayed. In H, the white vertices are the border vertices, while the black vertices are the core vertices.

A 2 Figure 2 :

 22 Figure 2: Proper 3-labellings of A 1 and A 2 with nb (3) = 1. The colours by c are indicated by integers within the vertices.

Observation 4 . 1 .

 41 mT(A 1 ) = 1.

  and so, {c (v 3 ), c (v 4 )} = {4, 5}. Assume, w.l.o.g., that c (v 3 ) = 4 and c (v 4 ) = 5. It follows that (v 2 v 3 ) = 1 and (v 2 v 4 ) = (v 3 v 4 ) = 2, and thus, c (v 2 ) ∈ {4, 5} = {c (v 3 ), c (v 4 )}, which contradicts that is proper.• Case 2: c (v 5 ) = 4. Then, v 5 has exactly one incident edge labelled 2. First, assume that (v 5 v 6 ) = 2. It follows that (v 3 v 5 ) = (v 4 v 5 ) = 1, and thus, {c (v 3 ), c (v 4 )} = {3, 5}.

Case 3 :

 3 c (v 5 ) = 5. Then, by Observation 2.5, the 2-labelling = sw( | A 1 , σ 1↔2 ) is also proper for A 1 . Moreover, recall that { (v 6 v 7 ), (v 6 v 8 )} = {1, 2}. It follows that can be extended to a proper 2-labelling of A 1 by setting (v 7 v 8 ) = 1. But then, c (v 5 ) = 4, and we get a contradiction to Case 2 above. • Case 4: c (v 5 ) = 6. Similarly to the previous case, the 2-labelling = sw( | A , σ 1↔2 ) is proper for A 1 and it can be extended to a proper 2-labelling of A 1 by setting (v 7 v 8 ) = 1. But then, c (v 5 ) = 3, and we get a contradiction to Case 1 above. Observation 4.2. mT(A 2 ) = 1. Proof. A proper 3-labelling of A 2 with nb (3) = 1 is depicted in Figure 2(b). Thus, mT(A 2 ) ≤ 1.

  and so, {c (v 4 ), c (v 5 )} = {4, 5}. Assume, w.l.o.g., that c (v 4 ) = 4 and c (v 5 ) = 5. It follows that (v 5 v 4 ) = (v 5 v 6 ) = 2 and (v 4 v 6 ) = 1, and thus, c (v 6 ) ∈ {4, 5} = {c (v 4 ), c (v 5 )}, which contradicts that is proper.• Case 2: c (v 3 ) = 4. Then, v 3 has exactly one incident edge labelled 2. First, assume that (v 3 v 2 ) = 2. It follows that (v 3 v 4 ) = (v 3 v 5 ) = 1,and thus, {c (v 4 ), c (v 5 )} = {3, 5}. Assume, w.l.o.g., that c (v 4 ) = 3 and c (v 5 ) = 5. Since c (v 4 ) = 3, we have that (v 4 v 5 ) = 1, and thus, c (v 5 ) ≤ 4, a contradiction. Then, assume, w.l.o.g., that (v 3 v 5 ) = 2 (and (v 3 v 2 ) = (v 3 v 4 ) = 1). It follows that c (v 5 ) ∈ {5, 6} and c (v 4 ) ∈ {3, 5}. If c (v 4 ) = 5, then c (v 5 ) = 6. This implies that (v 4 v 6 ) = (v 5 v 6 ) = 2, and thus, c (v 6 ) ∈ {5, 6} = {c (v 4 ), c (v 5 )}, a contradiction. Otherwise, c (v 4 ) = 3, and so, c (v 5 ) = 5 and c (v 6 ) = 4. Hence, (v 6 v 7 ) = (v 3 v 2 ) = 1, c (v 2 ), c (v 7 ) ∈ {3, 5} (because c (v 3 ) = c (v 6 ) = 4). We now get a contradiction no matter how v 1 v 2 , v 2 v 7 , and v 7 v 8 are labelled, as either c (v 2 ) = c (v 7 ) or 4 ∈ {c (v 2 ), c (v 7 )}.

Figure 3 :

 3 Figure 3: The planar graphs S 3 (left) and S g (right) of girth 3 and g, respectively.

Theorem 4 . 7 .

 47 There exist arbitrarily large connected planar graphs G with ρ 3 (G) ≥ 1/10.

Theorem 4 . 14 .

 414 If G is a nice cactus, then ρ 3 (G) ≤ 1/3.

Figure 4 :

 4 Figure 4: An example of a cactus G, with the corresponding cactus G -and the block graph B(G -), as they are introduced in the proof of Theorem 4.14. The black vertices of G -are cut vertices of G -. Observe that the leaves b B1 , b B4 , and b B7 of B(G -), correspond exactly to the cycles B 1 , B 4 , and B 7 of G (and of G -), which are considered as end-cycles of G, while B 5 is not considered as an end-cycle of G since b B5 is not a leaf of B(G -). Clearly, b B1 is at distance 10 from b B7 , while b B4 is at distance 6 from both b B1 and b B7 in B(G -).

Figure 5 :

 5 Figure 5: Proper 2-labellings for the two cases in the proof of Theorem 4.14, where the cactus G is one cycle C = (u, v, w, u) with one or two of its inner vertices having a pending edge attached.

  is a unicyclic spanning connected subgraph of G, in which the only cycle (being of odd length) is C x , to which is attached a hanging path (v x , v x+1 , . . . , v 0 ) containing all the other vertices of G. Since H is spanning, connected, and unicyclic, |E(H)| = |V (G)|, which is at most |E(G)| -3, since |E(G)| ≥ |V (G)| + 3.

Theorem 4 . 20 .

 420 If G is a Halin graph, then ρ 3 (G) ≤ 1/3.

4 Figure 8 :

 48 Figure 8: The proper 2-labelling for wheels of even order described in the proof of Theorem 4.20.

|M 1 | 3 + 1 ,

 131 + |M 2 | = |E(H )| -1 = |E(H)|, this gives nb (0) ≤ E(H) which is at most |E(G)|/3 since |E(G)| ≥ 3|V (G)|/2 and |V (G)| ≥ 6 (any Halin graph has at least 4 vertices, and the only Halin graph with exactly 4 vertices is K 4 , which we have already treated separately). That is,

  then v is a border vertex of both H 1 and H 2 . For a labelling of G and a subgraph H of G, we denote by | H the labelling of H inferred from , i.e., we have | H (e) = (e) for every edge e ∈ E(H).The key result is that, if a graph G contains other graphs H 1 , . . . , H n as pairwise disjoint weakly induced subgraphs, then the labelling properties of the H i 's, in particular mT(H i ), can be inferred to those of G: Lemma 3.1. Let G be a graph containing nice graphs H 1 , . . . , H n as pairwise disjoint weakly induced subgraphs. If is a proper 3-labelling of G, then | Hi is a proper 3-labelling of H i for every i ∈ {1, . . . , n}. Consequently, mT(G) ≥

	n i=1 mT(H i ).

A graph is locally irregular if no two of its adjacent vertices have the same degree.

Recall that a walk in a graph is a path in which vertices and edges can be repeated.

This work was supported by the ANR project DISTANCIA (ANR-17-CE40-0015). An extended abstract of parts of this paper has been presented in [3].

Lemma 4.3. Let G be a nice graph and let H be a graph with at least two vertices of degree 1 (at least one vertex of degree 1, respectively). Let G be the graph obtained by H-augmenting (Hattaching, respectively) p distinct edges (pending edges, respectively) of G (where 1 ≤ p ≤ |E(G)|). Then, mT(G ) ≥ p • mT(H).

Proof. This follows from Lemma 3.1 since G contains p copies H 1 , . . . , H p of H as pairwise disjoint weakly induced subgraphs.

The following theorem can be deduced from Lemma 4.3 since both graphs A 1 and A 2 have degree-1 vertices, verify the properties of Observations 4.1 and 4.2, and have 10 edges. Proof. Let p ≥ 1 be fixed. We construct a connected graph G with 10p edges such that nb (3) ≥ p for any proper 3-labelling of G, which implies that ρ 3 (G) ≥ 1/10. One possible construction (using A 2 ) is as follows. Start from any connected graph with p edges, and A 2 -augment all the p edges to get G. Then G has the claimed properties due to Observation 4.2 and Lemma 4.3.

Bounds for connected cubic graphs

Recall that, given a cubic graph G, it is NP-complete to decide whether χ Σ (G) ≤ 2 (see [START_REF] Dehghan | Algorithmic complexity of proper labeling problems[END_REF]). Then, a natural question to ask is whether they always admit proper 3-labellings assigning only a limited number of 3s. We prove that there is actually no p ≥ 1 such that the class of all cubic graphs lies in G ≤p . In contrast, we verify Conjecture 2.2 for this class of graphs.

First off, we note that the construction in the proof of Theorem 4.4 can be modified slightly to reach the same conclusion for cubic graphs. Proof. This follows from applying the same construction as in the proof of Theorem 4.4, but starting from a connected cubic graph with p edges, where p is a multiple of 3. In particular, note that A 2 is quasi 3-regular with exactly two degree-1 vertices (the ones that are used during the A 2 -augmentations), which implies that the resulting graph G is cubic.

Note that, through playing with A 2 -augmentations and the starting graph, we can go a bit beyond Theorem 4.5. For instance, since A 2 has exactly two cut vertices and each one is adjacent to one of its two degree-1 vertices, it can be checked that, performing the construction described in the proof of Theorem 4.5 starting from 2-connected cubic graphs, yields arbitrarily large 2connected cubic graphs G with ρ 3 (G) ≥ 1/10.

Regarding upper bounds, we prove that the parameter ρ 3 cannot exceed the 1/3 barrier in cubic graphs. In other words, we prove Conjecture 2.2 for these graphs.

Proof. We can assume that G is connected. Also, we can assume that G is neither K 4 (in which case the claim can be verified by hand) nor bipartite (due to Theorem 2.1). Thus, by Brooks' Theorem [START_REF] Brooks | On colouring the nodes of a network[END_REF], we know that Now assume u does not exist. We start by considering the cases where C 1 has length at least 6. Start by applying the labelling pattern 2, 1, 1, 2, 2, 1, 1, . . . to the edges of C 1 as before. Assume first that the two edges of C 1 incident to r get assigned distinct labels. Then, change the 1 assigned as a label to one of these two edges into a 3. As a result, no conflicts arise between inner vertices of C 1 , their colours are at most 5, while the colour of r is at least 6 due to the edge ru. So, the only possible conflict is between r and u. Suppose it occurs. Then, no conflict remains when assigning label 3 to the second edge of C 1 incident to r and we get a good labelling (in particular, only two edges of C 1 get assigned label 3 while its length is at least 6, and this assumption also guarantees that no two inner vertices of C 1 get in conflict). Lastly, assume that both edges of C 1 incident to r get assigned label 2 by the initial labelling scheme. Then, the colour of r is at least 5, which thus cannot be in conflict with its neighbours in C 1 . If r is not in conflict with u, then we get a good labelling of G.

Otherwise, we get one by changing the label of one of the two edges of C 1 incident to r to 3. All that remains to check are three length values for C 1 . The labelling schemes described below are illustrated in Figure 7.

-If C 1 has length 3 (see Figures 7(a),(b)), then assigning either labels 2, 1, 3 or 1, 1, 3 to the edges while going around, starting and ending with r, yields a good labelling, since r gets a colour of at least 6 or 5, respectively, while the inner vertices of C 1 get colours of at most 4, and the colour of u is the only other colour to avoid. In particular, note that these two labelling schemes increase the colour of r in two different ways (by 5 and 4, respectively). -If C 1 has length 4 (see Figures 7(c),(d)), then we get the same conclusion from applying the labelling scheme 2, 1, 1, 3 or 2, 1, 1, 2. Indeed, the inner vertices get colours of at most 4 and 3, respectively, while r gets a colour of at least 6 and 5, respectively. Also, these two schemes increase the colour of r differently, by 5 and 4, respectively.

-If C 1 has length 5 (see Figures 7(e),(f)), then the sequence 2, 1, 1, 2, 3 or 1, 2, 2, 1, 3 yields the same conclusion. Indeed, the inner vertices get colours of at most 5 and 4, respectively, while r gets a colour of at least 6 and 5, respectively. Also, these two schemes increase the colour of r differently, by 5 and 4, respectively.

In all cases, we can deduce a good labelling of G, which concludes the proof.

Bounds for other graph classes

In this section, we state, in the same spirit as in the previous subsections, some lower or upper bounds on ρ 3 that can be obtained for other classes of graphs that are 3-chromatic. Indeed, we focus on outerplanar graphs and Halin graphs. Note that, strictly speaking, Halin graphs are 4-colourable, but the main part of our proof will treat the 3-chromatic ones (see upcoming Section 4.5.2 for more details). The difference in this section is that for the considered graph classes, one of the two bounds is partially missing.

Outerplanar graphs

Recall that a graph is outerplanar if it admits a planar embedding where all vertices lie on the outer face. First off, we can obtain a result similar to Theorem 4.4 for outerplanar graphs. Proof. For a p ≥ 1, we construct a connected outerplanar graph G with the same properties as in the proof of Theorem 4.4. One possible construction (using A 1 ) is as follows. To obtain G, start from a star with p edges, and A 1 -attach all of its p edges. Again, G has the claimed labelling properties due to Observation 4.1 and Lemma 4.3. Also, note that G is clearly outerplanar, since the same holds true for every star, as well as A 1 .

Recall as well that outerplanar graphs form a subclass of series-parallel graphs. Thus, Theorem 4.18 also holds for arbitrarily large connected series-parallel graphs.

Note however that the outerplanar graphs constructed above have cut vertices. So the question remains, whether or not this lower bound still holds when considering 2-connected outerplanar graphs (recall that outerplanar graphs are 2-degenerate, and thus, each of them is either separable or 2-connected). As for an upper bound, we can prove the following:

Proof. We can assume that G is not bipartite, as otherwise the claim follows from Theorem 2.1. Then, χ(G) = 3 since outerplanar graphs are 2-degenerate. Now, if |V (G)| is odd, then the result follows from Corollary 3.8. So, in what follows, we assume that |V (G)| is even.

In 2-connected outerplanar graphs, the outer face forms a Hamiltonian cycle (v 0 , . . . , v n-1 , v 0 ). The other edges, which do not lie on the outer face, are called chords. Since G is not bipartite, it has an odd-length cycle C x . Since |V (G)| is even, this C x is not the whole outer cycle of G. Furthermore, we can assume that C x consists of consecutive vertices of the outer face, i.e., that C x = (v a , v a+1 , . . . , v a+x-1 , v a ) for some a ∈ {0, . . . , n-1} (where, here and in what follows, indices are taken modulo n), or, in other words, that v a v a+x-1 is the only chord of G in C x . Indeed, assume C x has at least two chords, one of which is v i v j , where i < j. Note that {v i , v j } is a cut set of G. This means that V (C x ) is fully included in either {v j , v j+1 , . . . , v i } or {v i , v i+1 , . . . , v j }. Assume that V (C x ) ⊆ {v j , v j+1 , . . . , v i } (the other case being symmetrical). Then, note that |{v i , v i+1 , . . . , v j }| must be even, as otherwise (v i , v i+1 , . . . , v j , v i ) would be an odd-length cycle as desired. Now, we note that replacing v i v j in C x by the path (v i , v i+1 , . . . , v j ) results in another odd-length cycle of G with one less chord. Repeating this process as long as the resulting odd-length cycle has more than one chord, eventually we end up with an odd-length cycle of G with only one chord, which is as desired.

Up to relabelling the vertices, we can assume, w.l.o.g., that C x = (v 1 , . . . , v x , v 1 ). Let us consider H, the subgraph of G containing the x edges of C x , and all the (other) edges of the Hamiltonian cycle (v 0 , . . . , v n-1 , v 0 ) on the outer face of G except for the edge v 0 v 1 . Note that H