, While there exists an induced subgraph of G isomorphic to P 3 = (u, x, v) such that u, v ? A and c (u) = c (v) = p, swap (ux) with (vx)

, the i th iteration of Step 1, c i+1 (u) = p and c i+1 (v) = p for all i ? 1. Indeed, their colours were p before the step was executed but since (ux) = (vx) for all these pairs u, v ? A (x is incident to exactly one edge with label j for all 1 ? j ? k), their colours cannot be p after the step is executed. Also, only the labels of edges incident to the vertices u and v are changed and so, the edges whose labels are changed at each execution of Step 1 are all disjoint. The second thing is that, for every vertex u ? B, we have c (u) = p. The third thing is that, once Step 1 can no longer be executed, for any two vertices u, v ? A such that c (u) = c (v) = p

, (b) else, swap (vy) with (yz) if this results in c (z) = p

, c) else, swap (ux) with (xz) and (vy) with (yz

, If one of Steps 2(a)-(c) is executed on the i th iteration of Step 2, then c i+1 (z) = p

, Moreover, after any of them is executed, each vertex in B is still incident to exactly one edge with each of the labels from 1 to k

, If Step 2(a) cannot be executed, then c i (z) ? i (xz) + i (ux) = p. Observe that i (ux) = i (xz) and i (vy) = i (yz) since x, y ? B and each of the vertices of B are still incident to exactly one edge with each of the labels from 1 to k (trivial induction on the number of times such a process has been performed before this step). Therefore, c i (z) ? i (xz) + i (ux) ? i (yz) + i (vy) = p ? i (yz) + i (vy) = p and so, then c i+1 (z) = p by definition

, Note that in all cases of Step 2, after its i th execution

. Moreover, Note that Step 2 eventually ends since no new vertices get colour p by Claim 4.3 and at least one vertex changes from colour p to another colour after each execution of Step 2. Once Step 2 can no longer be executed, for any two vertices u, v ? A such that c (u) = c (v) = p

, (b) else, swap (uy) with (yz) if this results in c (z) = p

, swap (ux) with (xz) and (uy) with (yz)

, This is a contradiction since both i (xz)? i (ux) = i (uy)? i (yz) and i (ux) ? i (xz) = i (uy) ? i (yz) hold if and only if i (xz) = i (ux), but i (xz) = i (ux) since x, y ? B and each of the vertices of B is still adjacent to exactly one edge with each of the labels from 1 to k, even after each iteration of Step 3 is executed until Step 3 can no longer be executed. Therefore, Step 3(a) or 3(b) was executable and so, Step 3(c) would not have been executed. Note that Step 3 eventually ends since no new vertices get colour p and one vertex changes from colour p to another colour after each execution of Step 3. Once Step 3 can no longer be executed, all cases of Step 3, after its i th iteration, we have c i+1 (u) = p, which is obvious except for in the case that Step 3(c) was executed

, The algorithm proceeds as follows: 4. While there exists an induced subgraph of G isomorphic to S 3 , with center u and leaves x, y, z such that u ? A and for all w ? N (u), we have that c (u) = c (w) = 6, (a) if for some w ? N (u) and some v ? N (w) \ {u}, swapping (uw) with (wv) results in c (v) = 6

, z but not incident to u such that, if this is the i th iteration of Step 4, then for all q ? N (x) \ {u}, for all r ? N (y) \ {u}, and for all s ? N (z) \ {u}, i+1 (xq) = i (uy), i+1 (yr) = i (uz

O. Baudon, M. Pil?niak, J. Przyby-lo, M. Senhaji, É. Sopena et al., Equitable neighbour-sum-distinguishing edge and total colourings, Discrete Applied Mathematics, vol.222, pp.40-53, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01330531

J. Bensmail, B. Li, B. Li, and N. Nisse, On Minimizing the Maximum Color for the 1-2-3 Conjecture, 2019.
URL : https://hal.archives-ouvertes.fr/hal-02330418

J. Bensmail, F. Fioravantes, and N. , Nisse On Proper Labellings of Graphs with Minimum Label Sum, 2020.

A. Dudek and D. Wajc, On the complexity of verterx-coloring edge-weightings, Discrete Mathematics Theoretical Computer Science, vol.13, issue.3, pp.45-50, 2011.

M. Kalkowski, M. Karo?ski, and F. Pfender, Vertex-coloring edge-weightings: towards the 1-2-3 Conjecture, Journal of Combinatorial Theory, Series B, vol.100, pp.347-349, 2010.

M. Karo?ski, T. Luczak, and A. Thomason, Edge weights and vertex colours, Journal of Combinatorial Theory, Series B, vol.91, pp.151-157, 2004.

D. König, Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre, Mathematische Annalen, vol.77, issue.4, pp.453-465, 1916.

W. Mulzer and G. Rote, Minimum-weight triangulation is NP-hard, Journal of the ACM, vol.55, issue.2, p.11, 2008.

J. Przyby-lo and M. Wo?niak, On a 1,2 Conjecture, Discrete Mathematics and Theoretical Computer Science, vol.12, issue.1, pp.101-108, 2010.

B. Seamone, The 1-2-3 Conjecture and related problems: a survey, 2012.

M. Senhaji, Neighbour-distinguishing decompositions of graphs, 2018.
URL : https://hal.archives-ouvertes.fr/tel-01962280

C. Thomassen, Y. Wu, and C. Zhang, The 3-flow conjecture, factors modulo k, and the 1-2-3-conjecture, Journal of Combinatorial Theory, Series B, vol.121, pp.308-325, 2016.