Domaine

J Araujo
email: julio.araujo@inria.fr

-J.-C Bermond

-F Giroire -F

-D Havet

Mazauric -R

Modrzejewski

J.-C Bermond

F Giroire

F Havet

D Mazauric
email: dorian.mazauric@inria.fr

R Modrzejewski
email: remigiusz.modrzejewski@inria.fr

Weighted Improper Colouring

Keywords: graph colouring, improper colouring, interference, radio networks, frequency assignment RR n°7590 coloration de graphes, coloration impropre, interférence, allocation de fréquences, réseaux radio

using integer linear programming, propose and test heuristic and exact Branchand-Bound algorithms on random cell-like graphs, namely the Poisson-Voronoi tessellations.

Thème : Réseaux, systèmes et services, calcul distribué Équipe-Projet Mascotte Rapport de recherche n°7590 -Juin 2012 -57 pages Abstract: In this paper, we study a colouring problem motivated by a practical frequency assignment problem and, up to our best knowledge, new. In wireless networks, a node interferes with other nodes, the level of interference depending on numerous parameters: distance between the nodes, geographical topography, obstacles, etc. We model this with a weighted graph (G, w) where the weight function w on the edges of G represents the noise (interference) between the two end-vertices. The total interference in a node is then the sum of all the noises of the nodes emitting on the same frequency. A weighted t-improper k-colouring of (G, w) is a k-colouring of the nodes of G (assignment of k frequencies) such that the interference at each node does not exceed the threshold t.

We consider here the Weighted Improper Colouring problem which consists in determining the weighted t-improper chromatic number defined as the minimum integer k such that (G, w) admits a weighted t-improper k-colouring. We also consider the dual problem, denoted the Threshold Improper Colouring problem, where, given a number k of colours, we want to determine the minimum real t such that (G, w) admits a weighted t-improper k-colouring. We first present general upper bounds for both problems; in particular we show a generalisation of Lovász's Theorem for the weighted t-improper chromatic number. We then show how to transform an instance of the Threshold Improper Colouring problem into another equivalent one where the weights are either one or M , for a sufficiently large M . Motivated by the original application, we then study a special interference model on various grids (square, triangular, hexagonal) where a node produces a noise of intensity 1 for its neighbours and a noise of intensity 1/2 for the nodes at distance two. We derive the weighted t-improper chromatic number for all values of t. Finally, we model the problem

Introduction

Let G = (V, E) be a graph. A k-colouring of G is a function c : V → {1, . . . , k}. The colouring c is proper if uv ∈ E implies c(u) = c(v). The chromatic number of G, denoted by χ(G), is the minimum integer k such that G admits a proper k-colouring. The goal of the Vertex Colouring problem is to determine χ(G) for a given graph G. It is a well-known NP-hard problem [START_REF] Karp | Reducibility among combinatorial problems[END_REF].

A k-colouring c is l-improper if |{v ∈ N (u) | c(v) = c(u)}| ≤ l, for all u ∈ V (as usual in the literature, N (u) stands for the set {v | uv ∈ E(G)}). Given a non-negative integer l, the l-improper chromatic number of a graph G, denoted by χ l (G), is the minimum integer k such that G admits an l-improper k-colouring. Given a graph G and an integer l, the Improper Colouring problem consists in determining χ l (G) and is also NP-hard [START_REF] Woodall | Improper colorings of graphs[END_REF][START_REF] Correa | About a Brooks-type theorem for improper colouring[END_REF]. Indeed, if l = 0, observe that χ 0 (G) = χ(G). Consequently, Vertex Colouring is a particular case of Improper Colouring.

In this work we define and study a new variation of the Improper Colouring problem for edge-weighted graphs. An edge-weighted graph is a pair (G, w) where G = (V, E) is a graph and w : E → R * + . Given an edge-weighted graph (G, w) and a colouring c of G, the interference of a vertex u in this colouring is defined by

I u (G, w, c) = {v∈N (u)|c(v)=c(u)} w(u, v).
For any non-negative real number t, called threshold, we say that c is a weighted t-improper k-colouring of (G, w) if c is a k-colouring of G such that I u (G, w, c) ≤ t, for all u ∈ V .

Given a threshold t ∈ R * + , the minimum integer k such that the graph G admits a weighted t-improper k-colouring is the weighted t-improper chromatic number of (G, w), denoted by χ t (G, w). Given an edge-weighted graph (G, w) and a threshold t ∈ R * + , determining χ t (G, w) is the goal of the Weighted Improper Colouring problem. Note that if t = 0 then χ 0 (G, w) = χ(G), and if w(e) = 1 for all e ∈ E, then χ l (G, w) = χ l (G) for any positive integer l. Therefore, the Weighted Improper Colouring problem is clearly NP-hard since it generalises Vertex Colouring and Improper Colouring.

On the other hand, given a positive integer k, we define the minimum kthreshold of (G, w), denoted by T k (G, w) as the minimum real t such that (G, w) admits a weighted t-improper k-colouring. Then, for a given edge-weighted graph (G, w) and a positive integer k, the Threshold Improper Colouring problem consists in determining T k (G, w). The Threshold Improper colouring problem is also NP-hard. This fact follows from the observation that determining whether χ l (G) ≤ k is NP-complete, for every l ≥ 2 and k ≥ 2 [START_REF] Cowen | Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency[END_REF][START_REF] Cowen | Defective coloring revisited[END_REF][START_REF] Correa | About a Brooks-type theorem for improper colouring[END_REF]. Consequently, in particular, it is a NP-complete problem to decide whether a graph G admits a weighted t-improper 2-colouring when all the weights of the edges of G are equal to one, for every t ≥ 2.

Motivation

Our initial motivation to these problems was the design of satellite antennas for multi-spot MFTDMA satellites [START_REF] Alouf | Quasi-optimal bandwidth allocation for multi-spot MFTDMA satellites[END_REF]. In this technology, satellites transmit signals to areas on the ground called spots. These spots form a grid-like structure which is modelled by an hexagonal cell graph. To each spot is assigned a radio channel or colour. Spots are interfering with other spots having the same channel and a spot can use a colour only if the interference level does not exceed a given threshold t. The level of interference between two spots depends on their distance. The authors of [START_REF] Alouf | Quasi-optimal bandwidth allocation for multi-spot MFTDMA satellites[END_REF] introduced a factor of mitigation γ and the interference of remote spots are reduced by a factor 1-γ. When the interference level is too low, the nodes are considered to not interfere anymore. Considering such types of interference, where nodes at distance at most i interfere, leads to the study of the i-th power of the graph modelling the network and a case of special interest is the power of grid graphs (see Section 3).

Related Work

Our problems are particular cases of the Frequency Assignment problem (FAP). FAP has several variations that were already studied in the literature (see [START_REF] Aardal | Models and solution techniques for frequency assignment problems[END_REF] for a survey). In most of these variations, the main constraint to be satisfied is that if two vertices (mobile phones, antennas, spots, etc.) are close, then the difference between the frequencies that are assigned to them must be greater than some function which usually depends on their distance.

There is a strong relationship between most of these variations and the L(p 1 , . . . , p d )-labelling problem [START_REF] Roger | A survey on labeling graphs with a condition at distance two[END_REF]. In this problem, the goal is to find a colouring of the vertices of a given graph G, in such a way that the difference between the colours assigned to vertices at distance i is at least p i , for every i = 1, . . . , d.

In some other variants, for each non-satisfied interference constraint a penalty must be paid. In particular, the goal of the Minimum Interference Frequency Assignment problem (MI-FAP) is to minimise the total penalties that must be paid, when the number of frequencies to be assigned is given. This problem can also be studied for only co-channel interference, in which the penalties are applied only if the two vertices have the same frequency. However, MI-FAP under these constraints does not correspond to Weighted Improper Colouring, because we consider the co-channel interference, i.e. penalties, just between each vertex and its neighbourhood.

The two closest related works we found in the literature are [START_REF] Mannino | An enumerative algorithm for the frequency assignment problem[END_REF] and [START_REF] Fischetti | Frequency assignment in mobile radio systems using branch-and-cut techniques[END_REF]. However, they both apply penalties over co-channel interference, but also to the adjacent channel interference, i.e. when the colours of adjacent vertices differ by one unit. Moreover, their results are not similar to ours. In [START_REF] Mannino | An enumerative algorithm for the frequency assignment problem[END_REF], they propose an enumerative algorithm for the problem, while in [START_REF] Fischetti | Frequency assignment in mobile radio systems using branch-and-cut techniques[END_REF] a Branch-and-Cut method is proposed and applied over some instances.

Results

In this article, we study both parameters χ t (G, w) and T k (G, w). We first present general bounds; in particular we show a generalisation of Lovász's Theorem for χ t (G, w). We after show how to transform an instance of Threshold Improper colouring into an equivalent one where the weights are either one or M , for a sufficiently large M . Motivated by the original application, we then study a special interference model on various grids (square, triangular, hexagonal) where a node produces a noise of intensity 1 for its neighbours and a noise of intensity 1/2 for the nodes that are at distance two. We derive the weighted t-improper chromatic number for all possible values of t.

Finally, we propose a heuristic and a Branch-and-Bound algorithm to solve Threshold Improper colouring for general graphs. We compare them to an integer linear programming formulation on random cell-like graphs, namely Voronoi diagrams of random points of the plan. These graphs are classically used in the literature to model telecommunication networks [START_REF] Baccelli | Stochastic geometry and architecture of communication networks[END_REF][START_REF] Gupta | The capacity of wireless networks. Information Theory[END_REF][START_REF] Haenggi | Stochastic geometry and random graphs for the analysis and design of wireless networks. Selected Areas in Communications[END_REF].

General Results

In this section, we present some results for Weighted Improper colouring and Threshold Improper colouring for general graphs and general interference models.

Upper bounds

Let (G, w) be an edge-weighted graph with positive real weights given by w : E(G) → Q * + . For any vertex v ∈ V (G), its weighted degree is d w (v) = u∈N (v) w(u, v). The maximum weighted degree of G is ∆(G, w) = max v∈V d w (v). Given a k-colouring c : V → {1, . . . , k} of G, we define, for every vertex v ∈ V (G) and colour i = 1, . . . , k, d i w,c (v) = {u∈N (v)|c(u)=i} (u, v). Note that d c(v) w,c (v) = I v (G, w, c). We say that a k-colouring c of G is w-balanced if c satisfies the following property:

For any vertex v ∈ V (G), I v (G, w, c) ≤ d j w,c (v), for every j = 1, . . . , k.

We denote by gcd(w) the greatest common divisor of the weights of w (observe that gcd(w) > 0 because we just consider positive weights). We use here the generalisation of the gcd to non-integer numbers (e.g. in Q) where a number x is said to divide a number y if the fraction y/x is an integer. The important property of gcd(w) is that the difference between two interferences is a multiple of gcd(w); in particular, if for two vertices v and u, d i w,c (v) > d j w,c (u), then d i w,c (v) ≥ d j w,c (u) + gcd(w). If t is not a multiple of the gcd(w), that is, there exists an integer a ∈ Z such that a gcd(w) < t < (a + 1)gcd(w), then χ w t (G) = χ w a gcd(w) (G).

Proposition 1. Let (G, w) be an edge-weighted graph. For any k ≥ 2, there exists a w-balanced k-colouring of G.

Proof. Let us colour G = (V, E) arbitrarily with k colours and then repeat the following procedure: if there exists a vertex v coloured i and a colour j such that d i w,c (v) > d j w,c (v), then recolour v with colour j. Observe that this procedure neither increases (we just move a vertex from one colour to another) nor decreases (a vertex without neighbour on its colour is never moved) the number of colours within this process. Let W be the sum of the weights of the edges having the same colour in their end-vertices. In this transformation, W has increased by d j w,c (v) (edges incident to v that previously had colour j in its endpoint opposite to v), but decreased by d i w,c (v) (edges that previously had colour i in both of their end-vertices). So, W has decreased by d i w,c (v)d j w,c (v) ≥ gcd(w). As W ≤ |E| max e∈E w(e) is finite, this procedure finishes and produces a w-balanced k-colouring of G.

The existence of a w-balanced colouring gives easily some upper bounds on the weighted t-improper chromatic number and the minimum k-threshold of an edge-weighted graph (G, w). It is a folklore result that χ(G) ≤ ∆(G) + 1, for any graph G. Lovász [START_REF] Lovász | On decompositions of graphs[END_REF] extended this result for Improper Colouring problem using w-balanced colouring. He proved that χ l (G) ≤ ∆(G)+1

l+1

. In what follows, we extend this result to weighted improper colouring.

Theorem 2. Let (G, w) be an edge-weighted graph with w : E(G) → Q * + , and t a multiple of gcd(w). Then χ t (G, w) ≤ ∆(G, w) + gcd(w) t + gcd(w) .

Proof. If t, ω, and G are such that χ t (G, ω) = 1, then the inequality is trivially satisfied. Thus, consider that χ t (G, ω) > 1.

Observe that, in any w-balanced k-colouring c of a graph G, the following holds:

d w (v) = u∈N (v) w(u, v) ≥ kd c(v) w,c (v). (1)
Let k * = ∆(G,w)+gcd(w) t+gcd(w)

≥ 2 and c * be a w-balanced k * -colouring of G.

We claim that c * is a weighted t-improper k * -colouring of (G, w). By contradiction, suppose that there is a vertex v in G such that c * (v) = i and that d i w,c (v) > t. Since c * is w-balanced, d j w,c (v) > t, for all j = 1, . . . , k * . By the definition of gcd(w) and as t is a multiple of gcd(w), it leads to d j w,c (v) ≥ t + gcd(w) for all j = 1, . . . , k * . Combining this inequality with Inequality (1), we obtain: ∆(G, w) ≥ d w (v) ≥ k * (t + gcd(w)), giving ∆(G, w) ≥ ∆(G, w) + gcd(w), a contradiction. The result follows.

Note that when all weights are unit, we obtain the bound for the improper colouring derived in [START_REF] Lovász | On decompositions of graphs[END_REF]. Brooks [START_REF] Brooks | On colouring the nodes of a network[END_REF] proved that for a connected graph G, χ(G) = ∆(G)+1 if, and only if, G is complete or an odd cycle. One could wonder for which edge-weighted graphs the bound we provided in Theorem 2 is tight. However, Correa et al. [START_REF] Correa | About a Brooks-type theorem for improper colouring[END_REF] already showed that it is NP-complete to determine if the improper chromatic number of a graph G attains the upper bound of Lovász, which is a particular case of Weighted Improper colouring, i.e. of the bound of Theorem 2.

We now show that w-balanced colourings also yield upper bounds for the minimum k-threshold of an edge-weighted graph (G, w). When k = 1, then all the vertices must have the same colour, and T 1 (G, w) = ∆(G, w). This may be generalised as follows, using w-balanced colourings. Theorem 3. Let (G, w) be an edge-weighted graph with w : E(G) → R * + , and let k be a positive integer. Then

T k (G, w) ≤ ∆(G, w) k .
Proof. Let c be a w-balanced k-colouring of G. Then, for every vertex v ∈ V (G):

kT k (G, w) ≤ kd c(v) w,c (v) ≤ d w (v) = u∈N (v) w(u, v) ≤ ∆(G, w)
Because T 1 (G, w) = ∆(G, w), Theorem 3 may be restated as kT k (G, w) ≤ . . . ≤ T 1 (G, w). This inequality may be generalised as follows.

Theorem 4. Let (G, w) be an edge-weighted graph with w : E(G) → R + , and let k and p be two positive integers. Then

T kp (G, w) ≤ T p (G, w) k .
Proof. Set t = T p (G, w). Let c be a t-improper p-colouring of (G, w). For i = 1, . . . , p, let G i be the subgraph of G induced by the vertices coloured i by c. By definition of improper colouring ∆(G i , w) ≤ t for all 1 ≤ i ≤ p. By Theorem 3, each (G i , w) admits a t/k-improper k-colouring c i with colours {(i -1)k + 1, . . . , ik}. The union of the c i 's is then a t/k-improper kp-colouring of (G, w).

Theorem 4 and its proof suggest that to find a kp-colouring with small impropriety, it may be convenient to first find a p-colouring with small impropriety and then to refine it. In addition, such a strategy allows to adapt dynamically the refinement. In the above proof, the vertex set of each part G i is again partitioned into k parts. However, sometimes, we shall get a better kp-colouring by partitioning each G i into a number of k i parts, with p i=1 k i = kp. Doing so, we obtain a T -improper kp-colouring of (G, w), where T = max{ ∆(Gi,w) ki , 1 ≤ i ≤ p}.

One can also find an upper bound on the minimum k-threshold by considering first the k -1 edges of largest weight around each vertex. Let (G, w) be an edge-weighted graph, and let v 1 , . . . , v n be an ordering of the vertices of G. The edges of G may be ordered in increasing order of their weight. Furthermore, to make sure that the edges incident to any particular vertex are totally ordered, we break ties according to the label of the second vertex. Formally, we say that

v i v j ≤ w v i v j if either w(v i v j ) < w(v i v j ) or w(v i v j ) = w(v i v j ) and j < j .
With such a partial order on the edge set, the set E k w (v) of min{|N (v)|, k -1} greatest edges (according to this ordering) around a vertex is uniquely defined. Observe that every edge incident to v and not in E k w (v) is smaller than an edge of E k (v) for ≤ w .

Let G k w be the graph with vertex set V (G) and edge set v∈V (G) E k w (v). Observe that every vertex of E k w (v) has degree at least min{|N (v)|, k -1}, but a vertex may have an arbitrarily large degree. For if any edge incident to v has a greater weight than any edge not incident to v, the degree of v in G k w is equal to its degree in G. However we now prove that at least one vertex has degree k -1. Proof. Suppose for a contradiction, that every vertex has degree at least k, then for every vertex x there is an edge xy in E(G k w )\E k w (x), and so in E k w (y)\E k w (x). Therefore, there must be a cycle (x 1 , . . . , x r ) such that, for all 1

1 1 u v u' K K v' w'(u,v)=w(u,v)-1 u v
≤ i ≤ r, x i x i+1 ∈ E k w (x i+1 ) \ E k w (x i ) (with x r+1 = x 1 ). It follows that x 1 x 2 ≤ w x 2 x 3 ≤ w • • • ≤ w x r x 1 ≤ w x 1 x 2 . Hence, by definition, w(x 1 x 2 ) = w(x 2 x 3 ) = • • • = w(x r x 1 ) = w(x 1 x 2 ).
Let m be the integer such that x m has maximum index in the ordering v 1 , . . . , v n . Then there exists j and j such that x m = v j and x m+2 = v j . By definition of m, we have j > j . But this contradicts the fact that x m x m+1 ≤ w x m+1 x m+2 . Corollary 6. If (G, w) is an edge-weighted graph, then G k w has a proper kcolouring.

Proof. By induction on the number of vertices. By Proposition 5, G k w has a vertex x of degree at most k -1. Trivially, G k w -x is a subgraph of (G -x) k w . By the induction hypothesis, (G -x) k w has a proper k-colouring, which is also a proper k-colouring of G k w -x. This colouring can be extended in a proper k-colouring of G k w , by assigning to x a colour not assigned to any of its k -1 neighbours.

Corollary 7. If (G, w) is an edge-weighted graph, then T k (G, w) ≤ ∆(G \ E(G k w ), w).

Transformation

In this section, we prove that the Threshold Improper Colouring problem can be transformed into a problem mixing proper and improper colouring. More precisely, we prove the following:

k (G , w ) = T k (G, w), but f (G , w ) = f (G, w) -1.
By repeating this operation f (G, w) times we get the required edge-weighted graph (G * , w * ).

RR n°7590

In case f (G, w) > 0, there exists an edge e = uv ∈ E(G) such that 2 ≤ w(e) < M . G is obtained from G by adding two complete graphs on k -1 vertices K u and K v and two new vertices u and v . We join u and u to all the vertices of K u and v and v to all the vertices of K v . We assign weight M to all these edges. Note that, u and u (v and v ) always have the same colour, namely the remaining colour not used in K u (resp. K v ).

We also add two edges uv and u v both of weight 1. The edges of G keep their weight in G , except the edge e = uv whose weight is decreased by one unit, i.e. w (e) = w(e) -1. Thus, f (G , ω ) = f (G, ω) -1 as we added only edges of weights 1 and M and we decreased the weight of e by one unit. Now consider a weighted t-improper k-colouring c of (G, w). We produce a weighted t-improper k-colouring c of (G , w ) as follows: we keep the colours of all the vertices in G, we assign to u (v ) the same colour as u (resp. v), and we assign to K u (resp. K v ) the k -1 colours different from the one used in u (resp. v).

Conversely, from any weighted improper k-colouring c of (G , w ), we get a weighted improper k-colouring c of (G, w) by just keeping the colours of the vertices that belong to G.

For such colourings c and c we have that

I x (G, w, c) = I x (G , w , c ), for any vertex x of G different from u and v. For x ∈ K u ∪ K v , I x (G , w , c ) = 0.
and therefore T k (G, w) = T k (G , w ).
In the worst case, the number of vertices of G * is n + m(w max -1)2k and the number of edges of

G * is m + m(w max -1)[(k + 4)(k -1) + 2] with n = |V (G)|, m = |E(G)| and w max = max e∈E(G) w(e).
In conclusion, this construction allows to transform the Threshold Improper Colouring problem into a problem mixing proper and improper colouring. Therefore the problem consists in finding the minimum l such that a (non-weighted) l-improper k-colouring of G * exists with the constraint that some subgraphs of G * must admit a proper colouring. The equivalence of the two problems is proved here only for integers weights, but it is possible to adapt the transformation to prove it for rational weights.

Squares of Particular Graphs

As mentioned in the introduction, Weighted Improper colouring is motivated by networks of antennas similar to grids [START_REF] Alouf | Quasi-optimal bandwidth allocation for multi-spot MFTDMA satellites[END_REF]. In these networks, the noise generated by an antenna undergoes an attenuation with the distance it travels. It is often modelled by a decreasing function of d, typically 1/d α or 1/(2 d-1 ).

RR n°7590

Here we consider a simplified model where the noise between two neighbouring antennas is normalised to 1, between antennas at distance two is 1/2 and 0 when the distance is strictly greater than two. Studying this model of interference corresponds to study the Weighted Improper colouring of the square of the graph G, that is the graph G 2 obtained from G by joining every pair of vertices at distance two, and to assign weights w 2 (e) = 1, if e ∈ E(G), and

w 2 (e) = 1/2, if e ∈ E(G 2 ) \ E(G).
Observe that in this case the interesting threshold values are the non-negative multiples of 1/2.

Figure 2 shows some examples of colouring for the square grid. In Figure 2(b), each vertex x has neither a neighbour nor a vertex at distance two coloured with its own colour, so I x (G 2 , w 2 , c) = 0 and G 2 admits a weighted 0-improper 5-colouring. In Figure 2(c), each vertex x has no neighbour with its colour and at most one vertex of the same colour at distance 2. So I x (G 2 , w 2 , c) = 1/2 and G 2 admits a weighted 0.5-improper 4-colouring.

For any t ∈ R + , we determine the weighted t-improper chromatic number for the square of infinite paths, square grids, hexagonal grids and triangular grids under the interference model w 2 . We also present lower and upper bounds for χ t (T 2 , w 2 ), for any tree T and any threshold t.

Infinite paths and trees

In this section, we characterise the weighted t-improper chromatic number of the square of an infinite path, for all positive real t. Moreover, we present lower and upper bounds for χ t (T 2 , w 2 ), for a given tree T .

Theorem 9. Let P = (V, E) be an infinite path. Then,

χ t (P 2 , w 2 ) =      3, if 0 ≤ t < 1; 2, if 1 ≤ t < 3; 1, if 3 ≤ t. Proof. Let V = {v i | i ∈ Z} and E = {(v i-1 , v i ) | i ∈ Z}.
Each vertex of P has two neighbours and two vertices at distance two. Consequently, the equivalence χ t (P 2 , ω 2 ) = 1 if, and only if, t ≥ 3 holds trivially.

There is a 2-colouring c of (P 2 , w 2 ) with maximum interference 1 by just colouring v i with colour (i mod 2) + 1. So χ t (P 2 , w 2 ) ≤ 2 if t ≥ 1. We claim that there is no weighted 0.5-improper 2-colouring of (P 2 , w 2 ). By contradiction, suppose that c is such a colouring

. If c(v i ) = 1, for some i ∈ Z, then c(v i-1 ) = c(v i+1 ) = 2 and c(v i-2 ) = c(v i+2 ) = 1. This is a contradiction because v i would have interference 1.
Finally, the colouring c(v i ) = (i mod 3) + 1, for every i ∈ Z, is a feasible weighted 0-improper 3-colouring.

Theorem 10. Let T = (V, E) be a (non-empty) tree. Then, ∆(T )-

t 2t+1 + 1 ≤ χ t (T 2 , w 2 ) ≤ ∆(T )-1 2t+1 + 2.
Proof. The lower bound is obtained by two simple observations. First, χ t (H, w) ≤ χ t (G, w), for any H ⊆ G. Let T be a tree and v be a node of maximum degree in T . Then, observe that the weighted t-improper chromatic number of the subgraph of T 2 induced by v and its neighbourhood is at least ∆(T )-t 2t+1 + 1.

RR n°7590

Indeed, the colour of v can be assigned to at most t vertices on its neighbourhood. Any other colour used in the neighbourhood of v cannot appear in more than 2t + 1 vertices because each pair of vertices in the neighbourhood of v is at distance two.

Let us look now at the upper bound. Choose any node r ∈ V to be the root of T . Colour r with colour 1. Then, by a breadth-first traversal in the tree, for each visited node v colour all the children of v with the ∆(T )-1 2t+1 colours different from the ones assigned to v and to its parent in such a way that at most 2t + 1 nodes have the same colour. This is a feasible weighted t-improper k-colouring of T 2 , with k ≤ ∆(T )-1 2t+1 + 2, since each vertex interferes with at most 2t vertices at distance two which are children of its parent.

For a tree T and the weighted function w 2 , Theorem 10 provides upper and lower bounds on χ t (T 2 , w 2 ), but we do not know the computational complexity of determining χ t (T 2 , w 2 ).

Grids

In this section, we show the optimal values of χ t (G 2 , w 2 ), whenever G is an infinite square, hexagonal or triangular grid, for all the possible values of t.

Square Grid

The square grid is the graph S in which the vertices are all integer linear combinations ae 1 + be 2 of the two vectors e 1 = (1, 0) and e 2 = (0, 1), for any a, b ∈ Z. Each vertex (a, b) has four neighbours: its down neighbour (a, b -1), its up neighbour (a, b + 1), its right neighbour (a + 1, b) and its left neighbour (a -1, b) (see Figure 2(a)).

Theorem 11.

χ t (S 2 , w 2 ) =                5, if t = 0; 4, if t = 0.5; 3, if 1 ≤ t < 3; 2, if 3 ≤ t < 8; 1, if 8 ≤ t.
Proof. If t = 0, then the colour of vertex (a, b) must be different from the ones used on its four neighbours. Moreover, all the neighbours have different colours, as each pair of neighbours is at distance two. Consequently, at least five colours are needed. The following construction provides a weighted 0-improper 5-colouring of (S 2 , w 2 ): for 0 ≤ j ≤ 4, let A j = {(j, 0) + a(5e 1 ) + b(2e 1 + 1e 2 ) | ∀a, b ∈ Z}. For 0 ≤ j ≤ 4, assign the colour j + 1 to all the vertices in A j (see Figure 2(b)).

When t = 0.5, we claim that at least four colours are needed to colour (S 2 , w 2 ). The proof is by contradiction. Suppose that there exists a weighted 0.5-improper 3-colouring of it. Let (a, b) be a vertex coloured 1. None of its neighbours is coloured 1, otherwise (a, b) has interference 1. If three neighbours have the same colour, then each of them will have interference 1. So two of its neighbours have to be coloured 2 and the two other ones 3 (see Figure 3

(c) 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 (d)
Figure 2: Optimal colourings of (S 2 , w 2 ): (b) weighted 0-improper 5-colouring of (S 2 , w 2 ), (c) weighted 0.5-improper 4-colouring of (S 2 , w 2 ), and (d) weighted 3-improper 2-colouring of (S 2 , w 2 ). (a + 1, b + 1). For all configurations, at least two of these four vertices have to be coloured 1 (the ones indicated by a * in Figure 3(a)). But then (a, b) will have interference at least 1, a contradiction. A weighted 0.5-improper 4colouring of (S 2 , w 2 ) can be obtained as follows (see Figure 2(c)): for 0 ≤ j ≤ 3, let B j = {(j, 0)+a(4e 1 )+b(3e 1 +2e 2 ) | ∀a, b ∈ Z} and B j = {(j +1, 2)+a(4e 1 )+ b(3e 1 +2e 2 ) | ∀a, b ∈ Z}. For 0 ≤ j ≤ 3, assign the colour j +1 to all the vertices in B j and in B j . If t = 1, there exists a weighted 1-improper 3-colouring of (S 2 , w 2 ) given by the following construction: for 0 ≤ j ≤ 2, let C j = {(j, 0) + a(3e 1 ) + b(e 1 + e 2 ) | ∀a, b ∈ Z}. For 0 ≤ j ≤ 2, assign the colour j + 1 to all the vertices in C j . Now we prove by contradiction that for t = 2.5 we still need at least three colours in a weighted 2.5-improper colouring of (S 2 , w 2 ). Consider a weighted 2.5-improper 2-colouring of (S 2 , w 2 ) and let (a, b) be a vertex coloured 1. Vertex (a, b) has at most two neighbours of colour 1, otherwise it will have interference 3. We distinguish three cases:

1. Exactly one of its neighbours is coloured 1; let (a -1, b) be this vertex. Then, the three other neighbours are coloured 2 (see Figure 3 A weighted 3-improper 2-colouring of (S 2 , w 2 ) can be obtained as follows: a vertex of the grid (a, b) is coloured with colour ( a 2 + b 2 mod 2) + 1, see Figure 2(d).

Finally, since each vertex has four neighbours and eight vertices at distance two, there is no weighted 7.5-improper 1-colouring of (S 2 , w 2 ) and, whenever t ≥ 8, one colour suffices.

Hexagonal Grid

There are many ways to define the system of coordinates of the hexagonal grid. Here, we use grid coordinates as shown in

χ t (H 2 , w 2 ) =          4, if 0 ≤ t < 1; 3, if 1 ≤ t < 2; 2, if 2 ≤ t < 6; 1, if 6 ≤ t.
Proof. Note first, that when t = 0, at least four colours are needed to colour the grid, because a vertex and its neighbourhood in H form a clique of size four in H 2 . The same number of colours are needed if we allow a threshold t = 0.5. To prove this fact, let A be a vertex cannot be coloured 2 because of the interference constraint in B and C. If F is coloured 3, then G and E are coloured 1, creating interference 1 in A. So F must be coloured 1 and G and E must be coloured 3. Then, H can be neither coloured 2 (interference in C) nor 3 (interference in E). So H is coloured 1. The vertex I is coloured 3, otherwise the interference constraint in H or in C is not satisfied. Then, J can receive neither colour 1, because of the interference in H, nor colour 2, because of the interference in C, nor colour 3, because of the interference in I.

There exists a construction attaining this bound and the number of colours, i.e. a 0-improper 4-colouring of (H 2 , w 2 ) as depicted in Figure 4. We define for 0 ≤ j ≤ 3 the sets of vertices A j = {(j, 0) + a(4e 1 ) + b(2e 1 + e 2 )|∀a, b ∈ Z}. We then assign the colour j +1 to the vertices in A j . This way no vertex experiences any interference as vertices of the same colours are at distance at least three.

For t = 1.5 it is not possible to colour the grid with less than three colours. By contradiction, suppose that there exists a weighted 1.5-improper 2-colouring. Consider a vertex A coloured 1. If all of its neighbours are coloured 2, they have already interference 1, so all the vertices at distance two from A need to be coloured 1; this gives interference 3 in A. Therefore one of A's neighbours, say D, has to be coloured 1 and consider that the other two neighbours B and C are coloured 2. B and C have at most one neighbour of colour 2. It implies that A has at least two vertices at distance two coloured 1. This is a contradiction, because the interference in A would be at least 2 (see Figure 6(b)).

Figure 5(a) presents a weighted 1-improper 3-colouring of (H 2 , w 2 ). To obtain this colouring, let B j = {(j, 0) + a(3e 1 ) + b(e 1 + e 2 ) | ∀a, b ∈ Z}, for 0 ≤ j ≤ 2. Then, we colour all the vertices in the set B j with colour j + 1, for every 0 ≤ j ≤ 2.

For t < 6, it is not possible to colour the grid with one colour. As a matter of fact, each vertex has three neighbours and six vertices at distance two in H. Using one colour leads to an interference equal to 6. There exists a 2-improper 2-colouring of the hexagonal grid as depicted in Figure 5(b). We define for 0 ≤ j ≤ 1 the sets of vertices C j = {(j, 0) + a(2e 1 ) + be 2 |∀a, b ∈ Z}. We then assign the colour j + 1 to the vertices in C j .

Triangular Grid

The triangular grid is the graph T whose vertices are all the integer linear combinations af 1 + bf 2 of the two vectors f 1 = (1, 0) and

f 2 = ( 1 2 , √ 3
2 ). Thus we may identify the vertices with the ordered pairs (a, b) of integers. Each vertex v = (a, b) has six neighbours: its right neighbour (a + 1, b), its right-up neighbour (a, b+1), its left-up neighbour (a-1, b+1), its left neighbour (a-1, b), its left-down neighbour (a, b -1) and its right-down neighbour (a + 1, b -1) (see Figure 8(a)).

Theorem 13.

χ t (T 2 , w 2 ) =                        7, if t = 0; 6, if t = 0.5; 5, if t = 1; 4, if 1.5 ≤ t < 3; 3, if 3 ≤ t < 5; 2, if 5 ≤ t < 12; 1, if 12 ≤ t.
Proof. If t = 0, there is no weighted 0-improper 6-colouring of (T 2 , w 2 ), since in T 2 there is a clique of size seven induced by each vertex and its neighbourhood. There is a weighted 0-improper 7-colouring of (T 2 , w 2 ) as depicted in Figure 7(a). This colouring can be obtained by the following construction: for 0 ≤ j ≤ 6, let A j = {(j, 0) + a(7f 1 ) + b(2f 1 + f 2 ) | ∀a, b ∈ Z}. For 0 ≤ j ≤ 6, assign the colour j + 1 to all the vertices in A j .

In what follows, we denote by V 0 a vertex coloured 1; by N 0 , N 1 , N 2 , N 3 , N 4 , N 5 the six neighbours of V 0 in T be in a cyclic order. Let Γ 2 be the set of twelve vertices at distance two of V 0 in T; more precisely N i(i+1) denotes the vertex of Γ 2 adjacent to both N i and N i+1 and by N ii the vertex of Γ 2 joined only to N i , for every 0 ≤ i ≤ 5, i + 1 is taken modulo 6 (see Figure 8(b)) and we denote by N ijk the vertex at distance three from V 0 adjacent to both N ij and N jk .

We claim that there is no weighted 0.5-improper 5-colouring of (T 2 , w 2 ). We prove it by contradiction, thus let c be such a colouring. No neighbour of V 0 can be coloured 1, otherwise I V0 (T 2 , w 2 , c) ≥ 1. As two consecutive neighbours are adjacent, they cannot have the same colour. Furthermore, there cannot be three neighbours with the same colour (each of them will have an interference at least 1). As there are four colours different from 1, exactly two of them, say 2 and 3, are repeated twice among the six neighbours. So, there exists a sequence of three consecutive neighbours the first one with a colour different from 2 and 3 and the two others coloured 2 and 3. W.l.o.g., let c(

N 5 ) = 4, c(N 0 ) = 2, c(N 1 ) = 3.
Note that the vertices coloured 2 and 3 have already an interference of 0.5, and so none of their vertices at distance two can be coloured 2 or 3. In particular, let A = {N 50 , N 00 , N 01 , N 11 , N 12 }; the vertices of A cannot be coloured 2 or 3. At most one vertex in Γ 2 can be coloured 1, otherwise I V0 (T 2 , w 2 , c) ≥ 1. If there is no vertex coloured 1 in A, we have a contradiction as we cannot have 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 4 5 1 2 3 4 5 1 2 3 4 5 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 (c) a sequence of five vertices uniquely coloured 4 and 5 (indeed colours should alternate and the vertex in the middle N 01 will have interference at least 1). Suppose N 4 is coloured 3, then N 45 and N 55 can only be coloured 1 and 5; but, as they have different colours, one is coloured 1 and so there is no vertex coloured 1 in A. So the second vertex coloured 3 in the neighbourhood of V 0 is necessarily N 3 (it cannot be N 2 neighbour of N 1 coloured 3). Then, N 4 cannot be also coloured 5, otherwise N 45 is coloured 1 and again there is no vertex coloured 1 in A. In summary c(N 4 ) = 2, c(N 3 ) = 3 and the vertex of Γ 2 coloured 1 is in A. But then the five consecutive vertices A = {N 23 , N 33 , N 34 , N 44 , N 45 } can only be coloured 4 and 5. A contradiction as I N34 (T 2 , w 2 , c) ≥ 1. A weighted 0.5-improper 6-colouring of (T 2 , w 2 ) can be obtained by the following construction (see Figure 7

1 2 3 1 2 3 1 2 3 1 2 3 1 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 1 2 3 1 2 3 1 2 3 2 3 1 2 3 1 2 3 1 2 3 1 3 1 2 3 1 2 3 1 2 3 1 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 (e) 1 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 2 1 2 2 1 2 1 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 2 1 2 (f)
(b)): for 0 ≤ j ≤ 11, let B j = {(j, 0) + a(12f 1 ) + b(2f 1 + f 2 ) | ∀a, b ∈ Z}.
For 0 ≤ j ≤ 5, assign the colour j + 1 to all the vertices in B j , B 6 with colour 2, B 7 with colour 1, B 8 with colour 4, B 9 with colour 3, B 10 with colour 6 and B 11 with colour 5. Now we prove that (T 2 , w 2 ) does not admit a weighted 1-improper 4-colouring. Again, by contradiction, suppose that there exists a weighted 1-improper 4colouring c of (T 2 , w 2 ). We analyse some cases:

1. There exist two adjacent vertices in T with the same colour.

Let V 0 and one of its neighbours be both coloured 1. Note that no other neighbour of V 0 , nor the vertices at distance two from V 0 are coloured 1 (otherwise, I V0 (T 2 , w 2 , c) > 1). We use intensively the following facts: Fact 1. There do not exist three consecutive vertices with the same colour (otherwise the vertex in the middle would have interference at least 2).

Fact 2. In a path of five vertices there cannot be four of the same colour (otherwise the second or the fourth vertex in this path would have interference at least 1.5).

One colour other than 1 should appear at least twice in the neighbourhood of V 0 . Let this colour be denoted 2 (the other colours being denoted 3 and 4).

I N0 (T 2 , w 2 , c) > 1 (respectively I N2 (T 2 , w 2 , c) > 1). One of N 3 and N 5 is not coloured 1, say N 3 . It is not coloured 2, otherwise I N3 (T 2 , w 2 , c) > 1. Let c(N 3 ) = 3. If N 4 or

No colour appears in two adjacent vertices of T.

Let V 0 be coloured 1. No colour can appear four or more times among the neighbours of V 0 , otherwise there are two adjacent neighbours with the same colour.

(a) One colour appears three times among the neighbours of

V 0 , say c(N 0 ) = c(N 2 ) = c(N 4 ) = 2. W.l.o.g., let c(N 1 ) = 3.
No vertex at distance two can be coloured 2. N 01 , N 11 and N 12 being neighbours of N 1 cannot be coloured 3 and they cannot be all coloured 4. So one of N 01 , N 11 , N 12 is coloured 1.

Similarly one of N 23 , N 33 , N 34 is coloured 1 (same reasoning with N 3 instead of N 1 ) and one of N 45 , N 55 , N 50 is coloured 1, so

I V0 (T 2 , w 2 , c) > 1.
(b) The three colours appear each exactly twice in the neighbourhood of V 0 .

i. The same colour appears in some N i and

N i+2 , 0 ≤ i ≤ 3. W.l.o.g., let c(N 0 ) = c(N 2 ) =

RR n°7590

Consequently, no matter the colour of N 44 some vertex will have interference greater than 1. ii. We have c(

N 0 ) = c(N 3 ) = 2, c(N 1 ) = c(N 4 ) = 3 and c(N 2 ) = c(N 5 ) = 4.
Here we find in each of the sets {N 50 , N 00 , N 01 } ,{N 12 , N 22 , N 23 } and {N 34 , N 44 , N 45 } a vertex coloured 1. Therefore I V0 (T 2 , w 2 , c) > 1, a contradiction.

To obtain a weighted 1-improper 5-colouring of (T 2 , w 2 ), for 0 ≤ j ≤ 4, let

C j = {(j, 0) + a(5f 1 ) + b(2f 1 + f 2 ) | ∀a, b ∈ Z}. For 0 ≤ j ≤ 4
, assign the colour j + 1 to all the vertices in C j . See Figure 7(c).

(T 2 , w 2 ) has a weighted 1.5-improper 4-colouring as depicted in Figure 7(d). Formally, this colouring can be obtained by the following construction: for 0

≤ j ≤ 3, let D j = {(j, 0) + a(4f 1 ) + b(f 1 + 2f 2 ) | ∀a, b ∈ Z};
then assign colour 4 to all the vertices in D 0 , 1 to all the vertices in D 1 , 3 to all the vertices in D 2 and 2 to all the vertices in D 3 . Now, for 0

≤ j ≤ 3, let D j = {(j, 1) + a(4f 1 ) + b(f 1 + 2f 2 ) | ∀a, b ∈ Z}.
Then, for 0 ≤ j ≤ 3, assign colour j + 1 to all the vertices in D j .

Let us prove that (T 2 , w 2 ) does not admit a weighted 2.5-improper 3-colouring. Suppose, by contradiction, that there exists a weighted 2.5-improper 3-colouring c of (T 2 , w 2 ). A vertex can have at most two neighbours of the same colour as it. Suppose again, w.l.o.g., that c(V 0 ) = 1. We use the following facts: We say that a vertex v is saturated, if we know that I v (T 2 , w 2 , c) ≥ 2.5. Let us analyse now each of these cases.

Case: V 0 has exactly two neighbours coloured 1.

We assume, w.l.o.g., that N 0 is coloured 1. We subdivide this case into three subcases according to the position of the second neighbour of V 0 coloured 1. Due to the symmetry, we analyse the three possible cases where respectively

N 1 , N 2 or N 3 is coloured 1. 1. Subcase c(N 1 ) = 1.
We now show that no colouring is feasible, for all possible different colourings of the vertices N 2 , N 3 , N 4 and N 5 (up to symmetries). We can have all these vertices of the same colour (Case 1a) or three of the same colour, say 2, and the other of colour 3 (Cases 1b and 1c) and two of colour 2 and two of colour 3 (Cases 1d, 1e and 1f). Observe that N 12 cannot be coloured 1. Let us study the two other cases: i. Now consider the case in which N 12 is coloured 2. We observe that N 2 and N 3 are saturated.

In case N 44 is coloured 1, we also have that V 0 is saturated and thus all the vertices N 22 , N 23 , N 33 and N 34 must be coloured Consider first the case c(N 22 ) = 1 (and thus V 0 is saturated). We have that N 23 , N 33 and N 34 must be coloured 3, thanks to the Facts 3 and 4 and V 0 being saturated. N 44 cannot be coloured 3 as we would have -If c(N 33 ) = 2, then N 3 is saturated. In this case, N 34 , N 44 and N 45 cannot be all coloured 3 (Fact 3). So one of them is coloured 1 and the two others are coloured 3 implying that V 0 and N 4 are saturated and N 55 and N 50 are both coloured 2. This is a contradiction as In order to avoid a P 5 of vertices coloured 3, N 00 must be coloured 2. Then, N 11 and N 12 must be coloured 3, due to the interference constraint in N 1 . Thanks to Fact 5, N 22 must be coloured 2 and so N 1 and N 3 are saturated. The vertices N 112 and N 233 cannot be coloured 3 as we would be in Case 1, then they are both coloured 1 and N 2 is also saturated. Consequently, N 122 must be coloured 3 and we reach a contradiction as I N12 (T 2 , w 2 , c) ≥ 3.

I N34 (T 2 , w 2 , c) ≥ 3. Since V 0 is also saturated, it implies that c(N 44 ) = 2.
I N5 (T 2 , w 2 , c) ≥ 3. -If c(N 33 ) = 1, then V 0 is saturated. In case N 34 is coloured 2, N
(b) Let us now suppose that c(N 3 ) = c(N 4 ) = 2 and c(N 5 ) = 3. We show that there is no feasible colour to N 44 by examining the three possible cases: i. Suppose first that N 44 is coloured 2. So N 4 is saturated and then, if c(N 55 ) = 3, as either N 45 or N 50 must be coloured 3, we are in Case 1. Thus, N 55 is coloured 1, V 0 is saturated and N 23 , N 33 , N 34 , N 45 and N 50 are coloured 3. Consequently, N 5 is saturated and so N 00 and N 01 are coloured 2. Thus, N 1 is saturated and N 12 and N 22 must be coloured 3, contradicting Fact 5. ii. Now consider that c(N 44 ) = 1. Thus, V 0 is saturated and N 34 is coloured 3, otherwise we would be in Case i. First consider that c(N 45 ) = 1 (V 0 is saturated If c(N 00 ) = 2, N 50 is saturated and thus N 01 must be coloured 3. Observe that N 550 and N 500 can neither be both coloured 1 (interference in N 0 ) nor 3 (interference in N 5 ). So one of these vertices is coloured 1 and the other is coloured 3. It implies that N 0 and N 3 are both saturated and thus that N 000 and N 001 must be both coloured 3. Then, N 11 and N 011 cannot receive colour 1 (N 0 is saturated) neither 3 (otherwise, I N01 (T 2 , w 2 , c) ≥ 3). So they are both coloured 2 and we reach a contradiction as I N1 (T 2 , w 2 , c) ≥ 3. We conclude that N 00 must be coloured 3. If N 01 is coloured 3, N 5 is saturated. In this case, N 550 and N 500 can neither be both coloured 1 (in-terference in N 0 ) nor 2 (Fact 3). So one of them is coloured 1 and the other is coloured 2 and, as a consequence, N 0 and N 50 are saturated. Thus, N 000 and N 001 must be both coloured 3 and we reach a contradiction to Fact 3. So we have that N 01 must be coloured 2 and c(N 11 ) = c(N 12 ) = 3, otherwise I N1 (T 2 , w 2 , c) ≥ 3. In this case, N 550 and N 500 cannot receive colour 2 (interference in N 50 ). They can neither be both coloured 1 (interference in N 0 ) nor 3 (interference in N 5 ). Thus, one of these vertices is coloured 1, the other is coloured 3 and N 0 and N 5 are saturated. It implies that one of the vertices N 000 or N 001 must be coloured 2 and the other is coloured 3, because they can neither be both coloured 2 (interference in N 01 ) nor 3 (interference in N 00 ). But then, N 00 is saturated and it implies that c(N 011 ) = 2. This leads to a contradiction as I N01 (T ). Thus, one of them is coloured 1 and the other is coloured 2. As a consequence, N 3 and N 45 are saturated. We obtain that N 233 and N 333 are both coloured 3. So N 33 cannot be coloured 3, as we are not in Case 1 and then c(N 23 ) = 3 and c(N 33 ) = 2. Recall that N 3 is saturated and thus N 12 and N 22 must be both coloured 3. This is a contradiction to Fact 5. Suppose now that c(N 44 ) = 1 (and thus that V 0 is saturated). -If c(N 34 ) = 3, then N 23 and N 33 can neither be both coloured 2 (interference in N 3 ) nor 3 (Fact 5). So one of them is coloured 2 and the other is coloured 3, implying that N 4 is saturated. Consequently, N 55 and N 50 must be coloured 2 and then that N 445 and N 455 must be both coloured 1 (otherwise, I N45 (T 2 , w 2 , c) ≥ 3). Thus, N 344 and N 444 are both coloured 2, due to the interference in N 44 . However, we get that I N45 (T 2 , w 2 , c) ≥ 3. -We conclude that N 34 is coloured 2 and thus that N 23 and N 33 must be both and N 33 must be coloured 1, otherwise they are all coloured 3 and we have I N23 (T 2 , w 2 , c) ≥ 3. So V 0 is also saturated and then N 55 must be coloured (e) Let us now consider the case c(N 4 ) = 2 and c(N 3 ) = c(N 5 ) = 3. We study now the subcases concerning to the colour of N 45 .

i. First consider that c(N 45 ) = 1. Recall that V 0 is saturated. In case N 44 is coloured 2, N 34 is coloured 3 and N 33 is coloured 2, as we are no longer in Case 1. N 55 and N 50 can neither be both coloured 2, otherwise I N4 (T 2 , w 2 , c) ≥ 3, nor 3, otherwise we would be in Case 1 with N 5 . So one of these vertices is coloured 2, the other is coloured 3 and N 4 is saturated. But then N 23 is coloured 3 and we are in Case 2d with central vertex N 3 . We conclude that N 44 is coloured 3.

-If N 34 is coloured 3, N 34 is saturated and c(N 23 ) = c(N 33 ) = 2. Then, N 22 is coloured 3, otherwise I N23 (T 2 , w 2 , c) ≥ 3, implying that N 3 is saturated. So c(N 12 ) = 2
and N 23 is also saturated. Thus, N 223 and N 233 are both coloured 1, N 2 is saturated, which implies that N 122 and N 222 must be coloured 3. Then, we are in Case 1. -So N 34 must be coloured 2. In case N 33 is also coloured 2, then we are in one of the cases from 2a to 2d with central vertex N 34 . Thus, N 33 must be coloured 3 implying that N 23 is coloured 2. N 12 and N 22 can neither be both coloured 2 (otherwise, I N23 (T 2 , w 2 , c) ≥ 3) nor 3 (otherwise,

I N3 (T 2 , w 2 , c) ≥ 3). So one is coloured 2, the other is coloured 3, N 3 is saturated and c(N 223 ) = c(N 233 ) = 1 (otherwise, I N23 (T 2 , w 2 , c) ≥ 3).
Thus, N 2 is also saturated. N 55 and N 50 cannot be both coloured 3, as we are not in Case 1. Consequently, (exactly) one of these vertices is coloured 2 and N 4 is saturated. It implies that N 334 and N 344 are coloured 1 and then N 333 must be coloured 2. Thus, N 23 is saturated and N 22 must be coloured 3 (otherwise, I N23 (T 2 , w 2 , c) ≥ 3). However, N 122 and N 222 must be coloured 3 and we are in Case 1 with vertex N 22 . By symmetry, we conclude that c(N 34 ) = 1. ii. Suppose now that N 45 is coloured 2. Observe that N 44 cannot be coloured 2 as we are no longer in Case 1.

Consider first the case c(N 44 ) = 1 (V 0 is saturated). If N 34 is coloured 2, N 4 is saturated, N 23 and N 33 are both coloured 3 and we are in Case 1 with N 3 . So N 34 is coloured 3 and N 33 must be coloured 2 (otherwise, Case 1 with N 3 ). N 55 and N 50 cannot be both coloured 3 (otherwise, Case 1 with N 5 ). So (exactly) one is coloured 2, N 4 is saturated and N 23 must be coloured 3. However, we are in Case 2d with central vertex N 3 . We conclude that N 44 must be coloured 3. Recall that c(N 34 ) = 1. In case N 34 is coloured 2, we are in Case 2c with N 4 instead of V 0 . So N 34 is coloured 3 and it is saturated. So c(N 23 ) = 3, c(N 33 ) = 3, among N 23 , N 33 , N 55 and N 50 at most one vertex is coloured 1 (interference in V 0 ) and at most two are coloured 2 (interference in N 4 ). Moreover, at most one of the vertices N 55 and N 50 is coloured 3, otherwise we are in Case 1 with N 5 . So, exactly one of the vertices N 55 and N 50 is coloured 3 and N 5 is saturated; exactly two of the vertices N 23 , N 33 , N 55 and N 50 are coloured 2 and N 4 is saturated. But then we find a contradiction to Fact 5 as N 334 , N 344 , N 444 , N 445 and N 455 are all coloured 1. iii. We then conclude that c(N 45 ) = 3 and by symmetry that c(N 34 ) = 3. N 44 cannot be coloured 3 by Fact 5. Suppose first that N 44 is coloured 1 (V 0 is saturated). Consequently, N 23 , N 33 , N 55 and N 50 must be coloured 2 due to the interference constraints in N 3 and N 5 . So N 4 is saturated and N 334 , N 344 , N 445 and N 455 must be coloured 1 due to the interference in N 34 and N 45 . This is a contradiction to Fact 5. We obtain that N 44 must be coloured 2. Among N 23 , N 33 , N 55 and N 50 at most one vertex is coloured 1 (interference in V 0 ) and none of them is coloured 3 (interference in N 3 and N 5 ). So at least 3 of them are coloured 2 and we get a contradiction as

I N4 (T 2 , w 2 , c) ≥ 3. (f) Now consider that c(N 3 ) = c(N 4 ) = c(N 5 ) = 3
. By Fact 3, we know that N 34 , N 44 and N 45 are not coloured 3. These vertices are also not coloured 1, otherwise we would be in one of the cases from 2a to 2e with vertex N 4 replacing of V 0 . So N 34 , N 44 and N 45 are all coloured 2. Let us check the possible colourings of N 55 .

i. First consider that N 55 is coloured 3. If N 50 is coloured 2, then we are in Case 2d with N 5 instead of V 0 . So N 50 is coloured 1 and V 0 are saturated. However, we obtain that N 23 and N 33 are both coloured 2 and we have a contradiction to Fact 5. ii. Suppose now that c(N 55 ) = 2. Observe that N 50 cannot be coloured 2, by Fact 5.

If c(N 50 ) = 1, V 0 is saturated and as N 44 is saturated we conclude that N 33 is coloured 3. But then N 3 and N 4 are saturated and we have a contradiction to Fact 5, because all the vertices N 334 , N 344 , N 444 , N 445 and N 455 must be coloured 1.

So N 50 is coloured 3 and N 4 , N 5 , N 44 and N 45 are saturated. Consequently, we find a contradiction to Fact 5 as N 344 , N 444 , N 445 , N 455 and N 555 are all coloured 1. iii. We conclude that c(N 55 ) = 1 and V 0 is saturated. N 23 and N 33 can neither be both coloured 2, nor 3, due to Facts 5 and 3, respectively. If N 23 is coloured 3 and N 33 is coloured 2, we have that N 4 , N 34 and N 44 are saturated. Thus, N 334 , N 344 , N 444 , N 445 and N 455 must be all coloured 1, contradicting Fact 5. Consequently, c(N 23 ) = 2 and c(N 33 ) = 3. But then we are in Case 2d with vertex N 3 replacing V 0 .

3. Subcase c(N 3 ) = 1.

Observe that the vertices N 01 , N 23 , N 34 and N 50 cannot be coloured 1, otherwise we would be in Case 2. Up to symmetries, we study the possible colourings of N 1 , N 2 , N 4 and N 5 : four of the same colour (Case 3a), three of the same colour (Case 3b) or two of the same colour (Cases 3c and 3d). Observe that among N 34 , N 44 and N 45 we have at most one vertex coloured 2, otherwise we would be in one of the Cases 1 or 2. Similarly, at most one of the vertices N 45 , N 55 and N 50 is coloured 3. In case there is a vertex coloured 2

among N 34 and N 44 , due to two vertices coloured 2 in the set {N 45 , N 55 , N 50 }, we have a contradiction as I N4 (T 2 , w 2 , c) ≥ 3. Observe that we cannot have all the vertices N 34 , N 44 and N 45 coloured 3 as we would be in Case 2. So, N 34 and N 44 are coloured 3 and N 45 is coloured 2. Since that there is a vertex in N 55 and N 50 coloured 2, we conclude that N 4 is saturated and then N 33 is coloured 3. This is a contradiction to Fact 5.

(c) We now study the case c(N 1 ) = c(N 2 ) = 2 and c(N 4 ) = c(N 5 ) = 3. By symmetry, we consider that the vertices N 00 , N 01 , N 11 , N 12 , N 22 and N 23 are not coloured 1. Then, the vertices N 11 , N 12 and N 22 must coloured 3, otherwise we would be in Cases 1 or 2. By the same reason, N 01 and N 12 must be coloured 2. As N 1 is saturated, N 00 is coloured 3. Consequently, we can neither colour N 50 with colours 1 or 3, because we would be in Case 2, nor colour it with colour 2, due to the interference in N 1 .

(d) Let us consider now that c(N 1 ) = 2, c(N 2 ) = 3 and that among N 4 and N 5 we have one vertex coloured 2 and the other is coloured 3. By symmetry, we can once more consider that the vertices N 00 , N 01 , N 11 , N 12 , N 22 and N 23 are not coloured 1.

i. In case N 12 is coloured 3, all the vertices N 11 , N 22 and N 23 must be coloured 2, otherwise we would be in Cases 1 or 2. So N 1 is saturated and N 00 and N 01 must be coloured 3. Then, as in Case 3c no feasible colour remains to colour N 50 . ii. Thus

N 12 is coloured 2. It implies that c(N 01 ) = c(N 11 ) = c(N 22 ) = 3,
otherwise we would be in Cases 1 or 2. Consequently, N 2 is saturated, N 23 and N 34 are coloured 2, and thus N 33 must be coloured 1. So N 3 is also saturated and N 223 and N 233 must be coloured 2. Then we are in Case 1 with N 23 .

Case: V 0 has exactly one neighbour coloured 1.

We also consider that no vertex v has two neighbours with its own colour, otherwise we can consider that v is V 0 and we are in the previous case. This fact is extensively used in this proof and many times it is omitted. W.l.o.g, let N 0 be the only neighbour of V 0 coloured 1 and let c(N 1 ) = 2.

1. Suppose first that c(N 2 ) = 2. Consequently, c(N 3 ) = 3, otherwise N 2 would have two neighbours coloured 2. We have three cases to analyse:

(a) In case c(N 4 ) = c(N 5 ) = 2, we claim that c(N 01 ) = c(N 50 ) = 3. In fact, if not, one of the vertices N 0 , N 1 or N 5 would have two neighbours with their colours. By the same reason, we conclude N 00 = 2. At this point, observe that N 1 and N 5 are saturated, thanks to the set {N 1 , N 2 , N 4 , N 5 , N 00 }. Consequently, the vertices N 11 and N 12 cannot receive colour 2 and they cannot be both coloured 3 as N 11 would have two neighbours with its colour. Similarly, we can conclude that at least one vertex of N 22 and N 33 is coloured 1 and also one of N 34 and N 44 and one of N 45 and N 55 . This is a contradiction because I V0 (T 2 , w 2 , c) ≥ 3.

(b) Suppose now that c(N 4 ) = 2 and c(N 5 ) = 3. Observe that c(N 01 ) = 3. By the hypothesis that no vertex has two neighbours with the same colour, we conclude that among the vertices N 11 and N 12 at least one of them is coloured 1, none of them can receive colour 2 and they cannot be both coloured 3.

RR n°7590

The same is valid for the vertices N 22 and N 23 . Observe also that these four vertices cannot be all coloured 1, otherwise I V0 (T 2 , w 2 , c) ≥ 3. Then consider that three of these vertices are coloured 1. Thus, since V 0 is saturated, we must be able colour the remaining vertices of Γ 2 with colours 2 and 3. If we consider that c(N 33 ) = 2, then all the other colours of vertices in Γ 2 are fixed by the hypothesis that each vertex has no two neighbours with its colour. One may check that, in this case, c(N 44 ) = c(N 55 ) = c(N 50 ) = 2. Thus, I N4 (T 2 , w 2 , c) ≥ 3, a contradiction. In case we colour N 33 with colour 3, one can check that there is no feasible colour for N 45 . Consequently, we conclude that among N 11 and N 12 there is one vertex coloured 1 and the other is coloured 3; and the same holds for vertices N 22 and N 23 . We now show by contradiction that no colour is feasible to N 55 .

i. First suppose that N 55 = 1. Thus, we already know that V 0 is saturated and we can no longer use colour 1 to colour vertices in Γ 2 . If we suppose that c(N 45 ) = 2, we observe that we cannot colour the vertices N 34 and N 44 with colours 2 and 3. Thus, let c(N 45 ) = 3. In this case, c(N 50 ) = c(N 44 ) = 2, c(N 34 ) = 3 and c(N 33 ) = 2. We observe that I N4 (T 2 , w 2 , c) ≥ 3, a contradiction. ii. Suppose now that c(N 55 ) = 2. Observe that N 45 cannot be coloured 2.

Suppose then that c(N 45 ) = 1. Again V 0 is saturated and we cannot have colour 1 in the remaining vertices of Γ In case N 44 is coloured 1, then N 34 is coloured 2, we observe that among N 23 and N 33 we have one vertex coloured 1 and the other is coloured 3. As a consequence, we get that V 0 and N 4 are saturated. Since c(N 334 ) = 1, no colouring is feasible for the vertex N 344 . If N 44 is coloured 2 (and so N 34 is coloured 1), observe that N 5 is saturated, since there is a vertex coloured 2 and another coloured 3 in the set {N 00 , N 01 } and we also find a vertex coloured 1 and another coloured 2 among vertices N 445 and N 455 . Consequently, the vertices N 555 and N 550 receive colours 1 and 3 (in some order). Thus, N 55 is saturated and then c(N 500 ) = 3. This is a contradiction as I N50 (T 2 , w 2 , c) ≥ 3. Since no other colouring is feasible for N 34 and N 44 as we cannot assign them the colour 3, we conclude that the colour of N 55 cannot be 1.

ii. Let us consider now the case c(N 55 ) = 2. It implies that c(N 50 ) = 3 and, consequently, the vertices N 00 and N 01 receive colours 2 and 3 in some order. Thus, N 5 is saturated. In case N 44 and N 45 are both coloured 1, the vertices N 34 , N 445 and N 455 must be all coloured 3. This is a contradiction as -If c(N 01 ) = 2, we can easily check that N 1 and N 5 are saturated. Observe also that N 0 is saturated as N 0 has a neighbour, the vertex V 0 , coloured 1 and 3 other vertices at distance two also coloured 1 which are N 45 , one vertex in the set {N 11 , N 12 } and another in the set {N 550 , N 500 }. Consequently, we reach a contradiction as N 001 and N 011 should be both coloured 3, but then N 001 would have two neighbours with colour 3. -Thus, c(N 01 ) = 3 in this case. It implies that c(N 500 ) = 1 and that the colour 3 does not appear in the vertices N 000 , N 001 and N 011 . These three vertices can also not be all coloured 1 or 2, as N 001 would have two neighbours of the same colour. We cannot have two of these vertices coloured 1 as we would have I N0 (T 2 , w 2 , c) ≥ 3. Consequently, in the set {N 000 , N 001 , N 011 } we have one vertex coloured 1 and two vertices coloured 2. This implies that N 0 and N 1 are saturated. We then reach a contradiction as no feasible colour remains to assign to N 11 . Then, we conclude that N 50 must be coloured 3 and then we get c(N 00 ) = 2 and c(N 01 ) = 3. Observe that if c(N 45 ) = 2, we have a contradiction as N 5 is saturated and all the vertices N 555 , N 550 and N 500 should be coloured 1. Thus we have that c(N 45 ) = 1. Observe that the vertices N 11 and N 12 cannot be both coloured the same, as we would either violate the interference constraint in N 0 (recall that there is one vertex coloured 1 in the set {N 550 , N 500 }) or we would have a vertex with two neighbours of the same colour. In case N 11 and N 12 are coloured 1 and 2, in any order, observe that since N 0 and N 1 are saturated, no colouring is feasible for the vertices N 001 and N 011 . We also have no feasible colouring for these vertices in case N 12 is coloured 1 (and then N 0 is saturated) or 2 (in this case N 1 is saturated) and the vertex N 11 is coloured 3. Thus, c(N 12 ) = 3 and suppose first that c(N 11 ) = 1. Since N 0 is saturated, the vertices N 000 , N 001 and N 011 can be just coloured 2 or 3. In case c(N 000 ) = 2, we obtain that c(N 001 ) = 3 and c(N 011 ) = 2. We reach a contradiction as I N00 (T 2 , w 2 , c) ≥ 3 (observe that one vertex among N 550 and N 500 is coloured 2). If c(N 000 ) = 3, we have that c(N 001 ) = 2 and c(N 011 ) = 3. Then, we also find a contradiction as I N01 (T 2 , w 2 , c) ≥ 3. Case: V 0 has no neighbour coloured 1.

I N4 (T 2 ,
Now we consider that no vertex has a neighbour with its own colour, otherwise we are in the previous case. W.l.o.g, we may conclude that c(N

0 ) = c(N 2 ) = c(N 4 ) = 2 and c(N 1 ) = c(N 3 ) = c(N 5 ) = 3. Thus, we obtain c(N 01 ) = c(N 12 ) = c(N 23 ) = c(N 34 ) = c(N 45 ) = c(N 50 ) = 1. This is a contra- diction as I V0 (T 2 , w 2 , c) ≥ 3.
Now we present the colouring providing the corresponding upper bound. For a weighted 3-improper 3-colouring of (T 2 , w 2 ) set, for 0

≤ j ≤ 2, E j = {(j, 0) + a(3f 1 ) + b(f 2 ) | ∀a, b ∈ Z}.
Then, for 0 ≤ j ≤ 2, assign the colour j + 1 to all the vertices in E j . See Figure 7(e). Now we prove that (T 2 , w 2 ) does not admit a weighted 4.5-improper 2colouring. Again, by contradiction, suppose that there exists a weighted 4.5improper 2-colouring c of (T 2 , w 2 ) with the interference function w 2 . A vertex can have at most four neighbours of the same colour as it. We analyse some cases:

1. There exists a vertex V 0 with four of its neighbours coloured with its own colour, say 1. Therefore among the vertices of Γ 2 at most one is coloured 1. Consider the two neighbours of V 0 coloured 2. First, consider the case in which they are adjacent and let them be N 0 and N 1 . In Γ 2 , N 0 has three neighbours and four vertices at distance two; since at most one being of colour 1, these vertices produce in N 0 an interference equal to 4 and as N 1 is also of colour 2, then I N0 (T 2 , w 2 , c) ≥ 5, a contradiction. In case the two neighbours of V 0 coloured 2 are non adjacent, let them be N i and N j . At least one of them, say N i has its three neighbours in Γ 2 coloured 2 and it has also at least three vertices at distance two in Γ 2 coloured 2; taking into account that N j is coloured 2 and at distance two from N i , we get I Ni (T 2 , w 2 , c) ≥ 5, a contradiction.

2.

No vertex has four neighbours with its colour and there exists at least one vertex V 0 coloured 1 that has three neighbours of the same colour 1.

0 ≤ j ≤ 1, let F j = {(j, 0) + a(2f 1 ) + b(f 1 + 2f 2 ) | ∀a, b ∈ Z} and F j = {(j -1, 1) + a(2f 1 ) + b(f 1 + 2f 2 ) | ∀a, b ∈ Z}.
Then, for 0 ≤ j ≤ 1, assign the colour j + 1 to all the vertices in F j and in F j . See Figure 7(f).

Since each vertex has six neighbours and twelve vertices at distance two in T, there is no weighted t-improper 1-colouring of (T 2 , w 2 ), for any t < 12. Obviously, there is a weighted 12-improper 1-colouring of T 2 .

Integer Linear Programming Formulations, Algorithms and Results

In this section, we look at how to solve the Weighted Improper colouring and Threshold Improper colouring for general instances inspired by the practical motivation. We present integer linear programming models for both problems. These models can be solved exactly for small sized instances using solvers like CPLEX1 . For larger instances, the solvers can take a prohibitive time to provide exact solutions. It is usually possible to obtain a sub-optimal solution stopping the solver after a limited time. If the time is too short, the quality of the solution may be unsatisfactory. Thus, we introduce two algorithmic approaches to find good solutions for Threshold Improper colouring in a short time: a simple polynomial-time greedy heuristic and an exact Branch-and-Bound algorithm. We compare the three methods on different sets of instances, among them Poisson-Voronoi tessellations as they are good models of antenna networks [START_REF] Baccelli | Stochastic geometry and architecture of communication networks[END_REF][START_REF] Gupta | The capacity of wireless networks. Information Theory[END_REF][START_REF] Haenggi | Stochastic geometry and random graphs for the analysis and design of wireless networks. Selected Areas in Communications[END_REF].

Integer Linear Programming Models

Given an edge-weighted graph G = (V, E, w), w : E → R * + , and a positive real threshold t, we model Weighted Improper Colouring by using two kinds of binary variables. Variable x ip indicates if vertex i is coloured p and variable c p indicates if colour p is used, for every 1 ≤ i ≤ n and 1 ≤ p ≤ l, where l is an upper bound for the number of colours needed in an optimal weighted t-improper colouring of G. l can be trivially chosen of value n, but a better value may be given by the results of Section 2. The model follows:

min l p=1 c p subject to ij∈E and j =i w(i, j)x jp ≤ t + M (1 -x ip ) ∀i ∈ V, 1 ≤ p ≤ l c p ≥ x ip ∀i ∈ V, 1 ≤ p ≤ l l p=1 x ip = 1 ∀i ∈ V x ip ∈ {0, 1} ∀i ∈ V, 1 ≤ p ≤ l c p ∈ {0, 1} 1 ≤ p ≤ l
where M is a large integer. For instance, it is sufficient to choose M > uv∈E w(u, v).

For Threshold Improper Colouring, given an edge-weighted graph G = (V, E, w), w : E → R * + , and a number of possible colours k ∈ N * , the model we consider is:

min t subject to ij∈E and j =i w(i, j)x jp ≤ t + M (1 -x ip ) ∀i ∈ V, 1 ≤ p ≤ l k p=1 x ip = 1 ∀i ∈ V x ip ∈ {0, 1} ∀i ∈ V, 1 ≤ p ≤ l
We give directly these models to the ILP solver CPLEX without using any preprocessing or any other technique to speed the search for an optimal solution.

Algorithmic approach

In this section, we show a Branch-and-Bound algorithm and a randomised greedy heuristic to tackle Threshold Improper colouring. Both are based on common procedures to determine the order in which vertices are coloured and colours are tried for a single vertex. Although, the Branch-and-Bound needs an ordering of the vertices to be coloured as input while the heuristic colours the vertices at the same time the order is being processed.

Order of vertices and colours

The order in which the vertices are chosen to be coloured follows essentially the same idea as the DSATUR algorithm, created by Daniel Brélaz [START_REF] Brélaz | New methods to color the vertices of a graph[END_REF].

Consider a graph G = (V, E, w), w : E → R * + and a partial colouring c : U → {1, . . . , k}, where U ⊆ V . We say that vertex v is coloured if v ∈ U , otherwise it is uncoloured. We define the total potential interference in vertex v to be:

I tot c,v = {u∈V |uv∈E and v / ∈U } w(u, v),
which is the sum of interferences for all colours induced in v by all its already coloured neighbours. The idea for both algorithms is to first colour vertices with highest total potential interference. Whenever more than one vertex has the highest total potential interference, one of them is chosen at random. At the beginning, when all vertices have I tot c,v = 0, one of the highest weighted degree is chosen instead.

Consider the following steps:

1. Colour a random vertex with maximal sum of incoming weights. 2. Colour a random vertex with maximal total potential interference.

3. If all vertices all coloured, stop. Otherwise, repeat step 2.

Note that the total potential interference does not depend on the actual colours assigned to the vertices. Thus, in order to decide which is the next vertex to be coloured, both algorithms, Branch-and-Bound and heuristic, use these three steps. However, the Branch-and-Bound algorithm needs an order to colour the vertices as input. So, we decide which order to give to the Branchand-Bound algorithm as input by running these three steps and using a single colour.

The procedure above specifies the order of vertices. For the order of colours to try, we define the potential interference in vertex v for colour x as: Anytime one of our algorithms colours a vertex, it tries the colours in order of increasing potential interference.

I c,v,x =

Branch-and-Bound Algorithm

Having an ordering procedure for both vertices and colours, we construct a simple Branch-and-Bound algorithm using them. The order of vertices to colour is fixed before running the algorithm, following the procedure in Section 4.2.1. Then, the ordered vertices are coloured by a recursive function that tries all the possible colours for each vertex as far as no interference constraint is violated. The order in which the colours are tried is also presented in the previous section. Our algorithm outputs all the feasible colourings it finds and, as all the possible colours are tried, the one using the minimum number of colours is an optimal one.

Here you have a pseudo code for the algorithm: Where by c ∩ (v ← x) we mean a partial colouring where colour of vertex v (which was uncoloured in c) is set to x, and colours of all other vertices are as in c. The algorithm is first called with all vertices uncoloured and t = ∞.

This algorithm displays a problematic behaviour. Imagine the partial colouring of the first few vertices yields good results locally, but implies a suboptimal interference at a more distant part of the graph. As the solution search takes exponential time in number of vertices, it is easy to envision that the time required to change the colouring of first vertices can be prohibitively long.

Greedy Heuristic

Here we propose a randomised greedy heuristic that, repeated multiple, but not exponentially many times, finds similar solutions to the above Branch-and-Bound without the mentioned problem. On the other hand, there are some solutions that are impossible to find with it, no matter the number of tries. An example of such an unobtainable solution is the optimal colouring of infinite square grid with 2 colours.

Note that there is substantial randomness in this algorithm. The first vertex is the one of the ones with highest weighted degree. In the extreme case of regular graphs, this already means any vertex at random. If we use the simple interference function defined in Section 3, then the second vertex is a random neighbour of the first vertex. Any time there are multiple vertices with maximum total potential interference, we choose one at random. Similarly, the choice of colours is also random in case of equal potential interference.

Above algorithm is first called with t = ∞. Whenever it returns a colouring, we set t = max v∈V I v (G, w, c) for further iterations. It is repeated for a given number of times, or until a time limit is reached. In all instances in the following sections the program is constrained by a time limit. This means that the algorithm is called for an unknown, but probably big number of times (e.g. for a 6-regular grid of 1024 vertices the program performs on average over 500 runs of the algorithm per second).

As a randomised greedy colouring heuristic, it has to be ran multiple times to achieve satisfactory results. This is not a practical issue due to low computational cost of each run. The local immutable colouring decision is taken in time O(k∆). Then, after each such decision, the interference has to be propagated, which takes linear time in the vertex degree. This gives a computational complexity bound O(kn∆)-time.

Validation

In this section we validate our algorithmic approaches at Threshold Improper colouring, by examining performance of their implementations. Tests cover a wide range of parameters, mostly on Delaunay graphs (see section 4.3.2).

Implementation

The ILP model is constructed out of the input graph and given directly to the CPLEX ILP solver. Branch-and-Bound algorithm is implemented in a straightforward way in the Python programming language. The greedy heuristic has a highly optimised implementation in the Cython programming language 2 .

In results displayed below, all programs are run simultaneously on the same quad-core enterprise-grade CPU. Both the Branch-and-Bound and greedy heuristic are limited to a single core. CPLEX is allowed to both the remaining cores.

Graphs

We consider random Delaunay graphs (dual of Voronoi diagram). This kind of graphs is an intuitive approximation of a network of irregular cells. To obtain a graph in this class, take a set of random points uniformly distributed over a square. These represent the vertices of the graph. To obtain the edges, compute a Delaunay triangulation. This can be done e.g. with Fortune's algorithm described in [START_REF] Fortune | A sweepline algorithm for voronoi diagrams[END_REF] in O(n log n) time.

See Figure 9(a) for a depiction of a fragment of such graph. Vertices are arranged according to the positions of original random points. Dotted lines Note that, to follow the model of the physical motivation, we are dealing with very sparse graphs. The average degree in Delaunay graph G converges to six (this results follows from the observation that G is planar and triangulated, thus |E(G)| = 3|V (G)| -6 by Euler's formula). To get an idea about the proposed algorithms' performance in denser graphs, we also run some tests on Erdös-Rényi graphs with expected degree equal to 50.

The interference model we consider in all experiments is the one described in Section 3: adjacent nodes interfere by 1 and nodes at distance two interfere by 1/2.

Results

Figure 9 shows a performance comparison of the above-mentioned algorithms. For all the plots, each data point represents an average over a number (between 24 and 100) of different graphs. The experiment procedure is as follows. For each graph size considered in an experiment, a number of graphs is generated. Each of those graphs is transformed into a set of instances, one for each desired number of allowed colours. All the programs are run on each instance, once for each desired value of time limit. Finally, a data point is created with results and all the parameters, averaged over the number of graphs.

Figures 9(b) and 9(c) plot how results for a problem instance get enhanced with increasing time limits. Plot 9(d) shows how well all the programmes scale with increasing graph sizes. Plots 9(e) and 9(f) show decreasing interference along increasing the number of colours allowed.

One immediate observation about both the heuristic and Branch-and-Bound algorithm is that they provide good solutions in relatively short time. On the other hand, with limited time, they fail to improve up to optimal results, especially with a low number of allowed colours. An example near-optimal solution found in around three minutes was not improved by Branch-and-Bound in over six days.

The heuristic, is able to provide good results in sub-second times and scales better with increasing graph sizes than the Branch-and-Bound. It is also not prone to spending a lot time exploring a sub-optimal branch of a decision tree. Still, in many cases it is unable to obtain optimal results and displays a worse end result than an integer linear program, given enough time.

Solving the ILP does not scale with increasing graph sizes as well as our simple algorithms. Furthermore, Figure 9(e) reveals one problem specific to ILP. When increasing the number of allowed colours, obtaining small interferences gets easier. But this introduces additional constraints in the formulation, thus increasing the complexity for a solver.

Proposed algorithms also work well for denser graphs. Figure 9(f) plots interferences for different numbers of colours allowed found by the programs for an Erdös-Rényi graph with n = 500 and p = 0.1. This gives us an average degree equal to 50. Both Branch-and-Bound and heuristic programs achieve acceptable, and nearly identical, results. But the large number of constraints makes the integer linear programming formulation very inefficient.

Conclusion, Open Problems and Future Directions

In this paper, we introduced and studied a new colouring problem, Weighted Improper Colouring. This problem is motivated by the design of telecommunication antenna networks in which the interference between two vertices depends on different factors and can take various values. For each vertex, the sum of the interferences it receives should be less than a given threshold value.

We first give general bounds on the weighted-improper chromatic number. We then study the particular case of infinite paths, trees and grids: square, hexagonal and triangular. For these graphs, we provide their weighted-improper chromatic number for all possible values of t. Finally, we propose a heuristic and a Branch-and-Bound algorithm to find good solutions of the problem. We compare their results with the one of an integer linear programming formulation on cell-like networks, Poisson-Voronoi tessellations.

Many problems remain to be solved:

The study of the grid graphs, we considered a specific function where vertices at distance one interfere by 1 and vertices at distance two by 1/2. Other weight functions should be considered. e.g. 1/d 2 or 1/(2 d-1 ), where d is the distance between vertices.

Other families of graphs could be considered, for example hypercubes.

We showed that the Threshold Improper Colouring problem can be transformed into a problem with only two possible weights on the edges 1 and ∞, that is a mix of proper and improper colouring. This simplify the nature of the graph interferences but at the cost of an important increase of instance sizes. We want to further study this. In particular, let G = (V, E, w) be an edge-weighted graph where the weights are all equal to 1 or M . Let G M be the subgraph of G induced by the edges of weight M ; is it true that if ∆(G M ) << ∆(G), then χ t (G, w) ≤ χ t (G) ≤ ∆(G,w)+1 t+1 ?

A similar result for L(p, 1)-labelling [START_REF] Havet | L(2,1)-labelling of graphs[END_REF] suggests it could be true.

Note that the problem can also be solved algorithmically for other classes of graphs and for other functions of interference. We started looking in this direction in [START_REF] Araujo | Weighted Improper Colouring[END_REF]. The problem can be expressed as a linear program and then be solved exactly using solvers such as CPLEX or Glpk3 for small instances of graphs. For larger instances, we propose a heuristic algorithm inspired by DSATUR [START_REF] Brélaz | New methods to color the vertices of a graph[END_REF] but adapted to the specifics of our colouring problem. We used it to derive colouring with few colours for Poisson-Voronoi tessellations as they are good models of antenna networks [START_REF] Baccelli | Stochastic geometry and architecture of communication networks[END_REF][START_REF] Gupta | The capacity of wireless networks. Information Theory[END_REF][START_REF] Haenggi | Stochastic geometry and random graphs for the analysis and design of wireless networks. Selected Areas in Communications[END_REF]. We plan to further investigate the algorithmic side of our colouring problem.

Figure 1 :Proposition 5 .

 15 Figure 1: Construction of G from G using edge uv ∈ E(G) and k = 4 colours. Dashed edges represent edges of weight M .

Theorem 8 .

 8 Let (G, w) be an edge-weighted graph where w is an integervalued function, and let k be a positive integer. We can construct an edgeweighted graph (G * , w * ) such that w * (e) ∈ {1, M } for any e ∈ E(G * ), satisfyingT k (G, w) = T k (G * , w * ), where M = 1 + e∈E(G) w(e).Proof. Consider the function f (G, w) = {e∈E(G)|w(e) =M } (w(e) -1).If f (G, w) = 0, all edges have weight either one or M and G has the desired property. In this case, G * = G. Otherwise, we construct a graph G and a function w such that T

  The neighbours of u with the same colour as u in G are the same as in G, except possibly v which has the same colour of u if, and only if, v has the same colour of u. Let = 1 if v has the same colour as u, otherwise = 0. As the weight of uv decreases by one and we add the edge uv of weight 1 in G , we get I u (G , w , c ) = I u (G, w, c) -+ w (u, v ) = I u (G, w, c). Similarly, I v (G , w , c ) = I v (G, w, c). Finally, I u (G , w , c ) = I v (G , w , c ) = . But I u (G , w , c ) ≥ (w(u, v) -1) and so I u (G , w , c ) ≤ I u (G , w , c ) and I v (G , w , c ) ≤ I v (G , w , c ). In summary, we have max x I x (G , w , c ) = max x I x (G, w, c)

  (a)). Now consider the four nodes (a -1, b -1), (a -1, b + 1), (a + 1, b -1) and

Figure 3 :

 3 Figure 3: Lower bounds for the square grid: (a) if t ≤ 0.5 and k ≤ 3, there is no weighted t-improper k-colouring of (S 2 , w 2 ); (b) the first case when t ≤ 2.5 and k ≤ 2, and (c) the second case.

2 .

 2 (b)). Consider the two sets of vertices {(a -1, b -1), (a + 1, b -1), (a, b -2)} and {(a -1, b + 1), (a + 1, b + 1), (a, b + 2)} (these sets are surrounded by dotted lines in Figure 3(b)); each of them has at least two vertices coloured 1, otherwise the vertex (a, b -1) or (a, b + 1) will have interference 3. But then (a, b) having four vertices at distance two coloured 1 has interference 3, a contradiction. Two neighbours of (a, b) are coloured 1. (a) These two neighbours are opposite, say (a -1, b) and (a + 1, b) (see Figure 3(c) left). Consider again the two sets {(a -1, b -1), (a + 1, b -1), (a, b -2)} and {(a -1, b + 1), (a + 1, b + 1), (a, b + 2)} (these sets are surrounded by dotted lines in Figure 3(c) left); they both contain at least one vertex of colour 1 and therefore (a, b) will have interference 3, a contradiction. (b) The two neighbours of colour 1 are of the form (a, b -1) and (a -1, b) (see Figure 3(c) right). Consider the two sets of vertices {(a + 1, b -1), (a + 1, b + 1), (a+2, b)} and {(a+1, b+1), (a-1, b+1), (a, b+2)} (these sets are surrounded by dotted lines in Figure 3(c) right); these two sets contain at most one vertex of colour 1, otherwise (a, b) will have interference 3. Moreover, each of these sets cannot be completely coloured 2, otherwise (a + 1, b) or (a, b + 1) will have interference at least 3. So vertices (a + 1, b -1), (a + 2, b), (a, b + 2) and (a -1, b + 1) are of colour 2 and the vertex (a + 1, b + 1) is of colour 1. But then (a -2, b) and (a -1, b -1) are of colour 2, otherwise (a, b) will have interference 3. Thus, vertex (a -1, b) has exactly one neighbour coloured 1 and we are again in Case 1. 3. All neighbours of (a, b) are coloured 2. If one of these neighbours has itself a neighbour (distinct from (a, b)) of colour 2, we are in Case 1 or 2 for this neighbour. Therefore, all vertices at distance two from (a, b) have colour 1 and the interference in (a, b) is 4, a contradiction.

Figure 4 .

 4 The hexagonal grid graph is then the graph H whose vertex set consists of pairs of integers (a, b) ∈ Z 2 and where each vertex (a, b) has three neighbours: (a -1, b), (a + 1, b), and (a, b + 1) if a + b is odd, or (a, b -1) otherwise. Theorem 12.

  (a, b) of H and B = (a-1, b), C = (a, b-1) and D = (a+1, b) be its neighbours in H. Denote by G = (a-2, b), E = (a-1, b-1), F = (a -2, b -1), H = (a + 1, b -1), I = (a + 2, b -1) and J = (a + 1, b -2) (see Figure 6(a)). By contradiction, suppose there exists a weighted 0.5-improper 3-colouring of H 2 . Consider a node A coloured 1. Its neighbours B, C, D cannot be coloured 1 and they cannot all have the same colour. W.l.o.g., suppose that two of them B and C have colour 2 and D has colour 3. Then E, F and G RR n°7590

Figure 4 :

 4 Figure 4: Weighted 0-improper 4-colouring of (H 2 , w 2 ). Left: Graph with coordinates. Right: Corresponding hexagonal grid in the euclidean space.

1 (b) t = 2 , k = 2 Figure 5 :

 1225 Figure 5: (a) weighted 1-improper 3-colouring of (H 2 , w 2 ) and (b) weighted 2-improper 2-colouring of (H 2 , w 2 ).

Figure 6 :

 6 Figure 6: Lower bounds for the hexagonal grid. (a) when t ≤ 0.5 and k ≤ 3, there is no weighted t-improper k-colouring of (H 2 , w 2 ); (b) vertices coloured 2 force a vertex coloured 1 in each ellipse, leading to interference 2 in central node.

Figure 7 :Figure 8 :

 78 Figure 7: Optimal colourings of (T 2 , w 2 ): (a) weighted 0-improper 7-colouring, (b) weighted 0.5-improper 6-colouring, (c) weighted 1-improper 5-colouring, (d) weighted 1.5-improper 4-colouring, (e) weighted 3-improper 3-colouring, and (f) weighted 5-improper 2-colouring.

  Two neighbours of V 0 coloured 2 are consecutive, say N 0 and N 1 . By Fact 1, N 2 is coloured 3 w.l.o.g. None of N 05 , N 00 , N 01 , N 11 , N 12 , N 22 and N 23 can be coloured 2, otherwise I N1 (T 2 , w 2 , c) > 1. One of N 12 , N 22 and N 23 is coloured 3, otherwise we contradict Fact 1 with colour 4 and at most one of N 01 , N 11 , N 12 , N 22 and N 23 is coloured 3, otherwise I N2 (T 2 , w 2 , c) > 1; but we have a contradiction with Fact 2. (b) Two neighbours of V 0 coloured 2 are at distance two, say N 0 and N 2 . Then N 50 , N 00 and N 01 (respectively N 12 , N 22 and N 23 ) are not coloured 2, otherwise

  (a). Therefore c(N 4 ) = 4 and c(N 5 ) = 3, by the same reason. But then c(N 23 ) = 4, otherwise the interference in V 0 or N 2 or N 3 is greater than 1. N 33 and N 34 can be only coloured 2, otherwise V 0 , N 3 , N 4 or N 23 will have interference strictly greater than 1, but N 33 has interference greater than 1, a contradiction. (c) Two neighbours of V 0 coloured 2 are at distance three say N 0 and N 3 . Then N 50 , N 00 and N 01 (respectively N 23 , N 33 and N 34 ) are not coloured 2, otherwise I N0 (T 2 , w 2 , c) > 1 (respectively I N3 (T 2 , w 2 , c) > 1). W.l.o.g., let N 1 be the vertex coloured 1. Among the four vertices N 12 , N 22 , N 44 and N 45 at most one is coloured 2, otherwise I N3 (T 2 , w 2 , c) > 1. So, w.l.o.g, we can suppose N 44 and N 45 are coloured 3 or 4; but we have a set of five consecutive vertices N 23 , N 33 , N 34 , N 44 , N 45 , contradicting Fact 2 (indeed at most one can be of the colour of N 4 ).

  2 and c(N 1 ) = 3. Then, c(N 3 ) = c(N 5 ) = 4 and c(N 4 ) = 3. Then, c(N 50 ) = 1 or 3, c(N 01 ) = 1 or 4. If c(N 50 ) = 3 and c(N 01 ) = 4, then c(N 00 ) = 1. Among N 50 , N 00 , N 01 , at least one has colour 1. Similarly one of N 12 , N 22 , N 23 has colour 1. So I V0 (T 2 , w 2 , c) ≥ 1 and c(N 34 ) = c(N 45 ) = 2.

Fact 3 .

 3 No vertex has three neighbours of the same colour.

Fact 4 .Fact 5 .

 45 If a vertex has two neighbours of the same colour, then it has at most one vertex at distance two with its colour. There is no path of five vertices of the same colour.

  (a) Suppose that c(N 2 ) = c(N 3 ) = c(N 4 ) = c(N 5 ) = 2. Observe that c(N 12 ) = c(N 50 ) = 3, thanks to Facts 3 and 5. Since N 3 and N 4 are saturated, we get that all the vertices N 22 , N 23 , N 33 , N 34 , N 44 , N 45 and N 55 cannot be coloured 2. At most one of these vertices is coloured 1, due to the interference in V 0 . W.l.o.g, we can then consider that c(N 22 ) = c(N 23 ) = c(N 33 ) = 3. But then, since N 23 and N 3 are saturated, we conclude that N 223 , N 233 , N 333 , N 334 and N 34 must be all coloured 1. This is a contradiction to Fact 5. (b) Now consider the case in which c(N 2 ) = c(N 3 ) = c(N 4 ) = 2 and c(N 5 ) = 3.

  Therefore, N 4 is saturated and so c(N 45 ) = c(N 55 ) = c(N 50 ) = 3, but then I N5 (T 2 , w 2 , c) ≥ 3. Thus, consider the case c(N 22 ) = 2. Then, N 2 and N 3 are saturated. One of the vertices N 33 , N 34 , N 44 and N 45 is coloured 1, thanks to Fact 5. So V 0 is saturated and c(N 01 ) = c(N 11 ) = c(N 23 ) = 3. Then, N 112 and N 122 cannot be coloured 3, otherwise I N12 (T 2 , w 2 , c) ≥ 3; they cannot be coloured 2 as N 2 is saturated; so c(N 112 ) = c(N 122 ) = 1, but then we reach a contradiction as I N1 (T

  2 , c) ≥ 3. c(N 22 ) = 3 and c(N 23 ) = 1. If N 33 is coloured 2, we observe that N 3 is saturated and N 34 , N 44 and N 45 must be all coloured 3. This contradicts Fact 3. We conclude that c(N 33 ) = 3. If N 34 is coloured 2, N 3 is saturated and N 44 and N 45 are both coloured 3. Then, N 4 is saturated and c(N 55 ) = c(N 50 ) = 2. This is a contradiction as I N5 (T 2 , w 2 , c) ≥ 3. Then, c(N 34 ) = 3 and then N 44 is coloured 2. If N 45 is coloured 3, N 4 is saturated and then N 55 and N 50 must be both coloured 2. This is a contradiction as I N5 (T 2 , w 2 , c) ≥ 3. So c(N 45 ) = 2 and N 5 is saturated. As a consequence, we get c(N 55 ) = c(N 50 ) = c(N 00 ) = c(N 01 ) = 3. This is another contradiction as I N50 (T 2 , w 2 , c) ≥ 3. c(N 22 ) = 3 and c(N 23 ) = 3. N 33 cannot be coloured 3 thanks to the interference constraint in N 23 .

2 .

 2 (d) Now, we study the case c(N 2 ) = c(N 3 ) = 2 and c(N 4 ) = c(N 5 ) = 3. Observe that colours 2 and 3 are symmetric under these hypothesis. In order to use this symmetry, let us consider the possible colourings of N 23 and N 45 (up to the symmetries):i. In case c(N 23 ) = 2 and c(N 45 ) = 3, observe that N 34 is necessarily coloured 1, thanks to Fact 3. Consequently, V 0 is saturated, N 33 is coloured 3 and N 44 is coloured 2. It implies that N 3 and N 4 are also saturated and that N 334 and N 344 are both coloured 1. As N 34 is also saturated, N 233 and N 333 are coloured 3. Moreover, N 22 is also coloured 3 as V 0 and N 3 are saturated. This is a contradiction as I N33 (T 2 , w 2 , c) ≥ 3. ii. Now consider that c(N 23 ) = 2 and c(N 45 ) = 2. Since N 3 is saturated and Fact 3 holds, among N 34 and N 44 we have one vertex coloured 1 and the other is coloured 3. So V 0 is saturated, N 33 is coloured 3 and N 4 is then saturated. Consequently, N 334 and N 344 are coloured 1 and N 55 and N 50 are coloured 2.N 444 can neither be coloured 3 as N 4 is saturated, nor 1 asI N344 (T 2 , w 2 , c) ≥ 3. So c(N 45 ) issaturated and N 445 and N 455 are both coloured 1. This is a contradiction as either I N34 (T 2 , w 2 , c) ≥ 3 or I N44 (T 2 , w 2 , c) ≥ 3. iii. Let us study the case c(N 23 ) = 2 and c(N 45 ) = 1. So, c(N 33 ) = c(N 34 ) = 3 and c(N 44 ) = 2. As N 3 , N 4 and N 34 are saturated, N 233 , N 333 , N 334 and N 344 are coloured 1. As N 3 is saturated, c(N 12 ) = c(N 22 ) = 3. N 4 and N 34 saturated imply that N 233 , N 333 , N 334 and N 344 are coloured 1. So, by Fact 5, c(N 233 ) = 3 and N 22 is saturated. Consequently, c(N 11 ) = 2 and N 2 is saturated. Therefore, c(N 112 ) = c(N 122 ) = 1, but we have a contradiction as I N1 (T 2 , w 2 , c) ≥ 3. iv. We now deal with the case c(N 23 ) = 1 and c(N 45 ) = 2. Observe that N 33 cannot be coloured 2, because in this case V 0 and N 3 are saturated RR n°7590and we would have a contradiction to Fact 3 as N 34 and N 44 should be both coloured 3. Consequently, N 33 is coloured 3. In case N 34 is coloured 3, N 4 is saturated and then N 45 , N 55 and N 50 are coloured 2. This is a contradiction as I N45 (T 2 , w 2 , c) ≥ 3. So c(N 34 ) = 2 and N 3 is saturated. As a consequence, N 44 is coloured 3 and N 4 is also saturated and the vertices N 55 and N 50 must be coloured 2. It implies that N 45 is saturated and c(N 344 ) = c(N 444 ) = c(N 445 ) = c(N 455 ) = 1. As N 3 and N 4 are saturated, N 334 should be also coloured 1, but this contradicts Fact 5. v. We now deal with the last subcase in which c(N 23 ) = 3 and c(N 45 ) = 2 (Recall that colours 2 and 3 are once more symmetric). If c(N 33 ) = 2, N 3 is saturated. Then N 34 and N 44 cannot receive colour 2, cannot be both coloured 1 (Fact 4 with V 0 ) and cannot be both coloured 3 (Fact 4 with N 4). -In case c(N 34 ) = 1 and c(N 44 ) = 3, N 4 and V 0 are saturated. Consequently, c(N 334 ) = c(N 344 ) = 1 and N 34 is also saturated. Thus, c(N 12 ) = c(N 22 ) = c(N 233 ) = c(N 333 ) = 3. This is a contradiction to Fact 5. -So c(N 34 ) = 3 and c(N 44 ) = 1. One more V 0 , N 3 and N 4 are saturated. It implies that c(N 12 ) = c(N 22 ) = 3 and then N 23 is also saturated. Consequently, the vertices N 233 , N 333 , N 334 and N 344 must be all coloured 1. This contradicts Fact 5. As c(N 33 ) = 2, by symmetry, we conclude that c(N 44 ) = 3. We use this information in the following subcase. If c(N 33 ) = 3, observe that N 34 cannot be coloured 3, thanks to Fact 5. Recall that N 44 is either coloured 1 or 2, by symmetry. Moreover, N 34 and N 44 cannot be both coloured 2 due to Fact 5. -In case c(N 34 ) = 2 and c(N 44 ) = 1, V 0 and N 3 are saturated. This implies that c(N 12 ) = c(N 22 ) = 3. This is a contradiction as I N23 (T 2 , w 2 , c) ≥ 3. -So c(N 34 ) = 1 and c(N 44 ) = 2. N 55 and N 50 cannot be both coloured 2, otherwise I N45 (T 2 , w 2 , c) ≥ 3. So one is coloured 3 and N 4 is saturated. Similarly, N 12 and N 22 cannot be both coloured 3, otherwise I N23 (T 2 , w 2 , c) ≥ 3. Thus, one of them is coloured 2 and N 3 is saturated. Then, c(N 334 ) = c(N 344 ) = 1 and N 34 is saturated. Since N 3 is also saturated, we have that c(N 233 ) = c(N 333 ) = 3, but then I N33 (T 2 , w 2 , c) ≥ 3, a contradiction. As N 33 cannot be coloured 3, again by symmetry we conclude that N 44 cannot be coloured 2. Thus, we have a contradiction to Fact 4 in V 0 as c(N 33 ) = c(N 44 ) = 1. (e) Let us consider now that c(N 2 ) = c(N 4 ) = 2 and c(N 3 ) = c(N 5 ) = 3. By Facts 3 and 4, there is at most one vertex in Γ 2 coloured 1. By symmetry, we consider w.l.o.g. that this vertex is in {N 22 , N 23 , N 33 , N 34 }. So we know that N 44 , N 45 and N 55 are not coloured 1. i. c(N 34 ) = 1 (and then V 0 is saturated). c(N 44 ) = c(N 45 ) = 2. In this case, N 4 is saturated. So, c(N 23 ) = c(N 33 ) = c(N 55 ) = c(N 50 ) = 3 and N 3 and N 5 are saturated. We then reach a contradiction because c(N 334 ) = c(N 344 ) = c(N 445 ) = 1 and then I N34 (T 2 , w 2 , c) ≥ 3. c(N 44 ) = c(N 45 ) = 3. So N 45 is saturated and c(N 55 ) = c(N 50 ) = 2. Observe that N 23 and N 33 cannot be both coloured 3, otherwise I N3 (T 2 , w 2 , c) ≥ 3. If RR n°7590 both N 23 and N 33 are coloured 2, then N 4 is also saturated and then N 334 , N 444 , N 445 and N 455 are all coloured 1, contradicting Fact 5. So among N 23 and N 33 we have one vertex coloured 2 and the other is coloured 3 and, consequently, N 3 is saturated. So N 12 and N 22 are coloured 1 and we have a contradiction as I N2 (T 2 , w 2 , c) ≥ 3. Either c(N 44 ) = 2 and c(N 45 ) = 3, or c(N 44 ) = 3 and c(N 45 ) = 2. In this case, N 23 and N 33 cannot be both coloured 3, otherwise I N3 (T 2 , w 2 , c) ≥ 3. Similarly, N 55 and N 50 cannot be both coloured 3, otherwise I N5 (T 2 , w 2 , c) ≥ 3. At most two among N 23 , N 33 , N 55 and N 50 are coloured 2, otherwise I N4 (T 2 , w 2 , c) ≥ 3. Consequently, one vertex among N 23 and N 33 is coloured 2 and the other is coloured 3, the same happens for vertices N 55 and N 50 and, then, N 4 is saturated. N 12 and N 22 cannot be both coloured 2, otherwise I N2 (T 2 , w 2 , c) ≥ 3. So one of them is coloured 1 and N 3 is saturated, implying that c(N 334 ) = c(N 344 ) = 1 and N 34 is saturated. If c(N 45 ) = 3, then N 5 is saturated and c(N 445 ) = 1, but then I N34 (T 2 , w 2 , c) ≥ 3. If c(N 45 ) = 2, we have that c(N 44 ) = 3. N 444 and N 445 cannot be both coloured 3, otherwise I N44 (T 2 , w 2 , c) ≥ 3. So one of them is coloured 3 and again I N34 (T 2 , w 2 , c) ≥ 3. ii. c(N 34 ) = 2. Recall that N 44 , N 45 and N 55 are not coloured 1. Observe that, by Fact 3, at most one of N 44 and N 45 is coloured 2. If one of these vertices is coloured 2, N 4 is saturated and N 55 and N 50 must be both coloured 1. It implies a contradiction as I N5 (T 2 , w 2 , c) ≥ 3. Consequently, N 44 and N 45 are both coloured 3 and N 45 is saturated. So N 55 and N 50 are coloured 2 and N 4 is also saturated implying that c(N 344 ) = c(N 444 ) = c(N 445 ) = c(N 455 ) = 1. Since N 444 is saturated, N 334 must be coloured 3 and then N 23 and N 33 cannot receive colour 3, otherwise I N3 (T 2 , w 2 , c) ≥ 3. We obtain a contradiction because N 23 and N 33 are both coloured 1 and I V0 (T 2 , w 2 , c) ≥ 3. iii. c(N 34 ) = 3. Observe that N 44 and N 45 cannot be both coloured 3, due to Fact 5. c(N 44 ) = c(N 45 ) = 2. In this case, N 4 is saturated and then N 55 and N 50 must be coloured 3. This is a contradiction because I N5 (T 2 , w 2 , c) ≥ 3. c(N 44 ) = 2 and c(N 45 ) = 3. Due to the interference in N 5 , we have that c(N 55 ) = c(N 50 ) = 2 and then N 4 is saturated. However, the vertices N 23 and N 33 cannot receive colour 3, due to the interference in N 3 , and so they are both coloured 1 and we have a contradiction as I V0 (T 2 , w 2 , c) ≥ 3. c(N 44 ) = 3 and c(N 45 ) = 2. In this case, N 34 is saturated. If N 23 and N 33 are both coloured 2, N 4 is saturated and N 55 and N 50 must be coloured 3 and we get I N5 (T 2 , w 2 , c) ≥ 3. So among N 23 and N 33 we have one vertex coloured 1 and the other is coloured 2. N 55 and N 50 can neither be both coloured 3, otherwise I N5 (T 2 , w 2 , c) ≥ 3, nor both coloured 2, otherwise I N4 (T 2 , w 2 , c) ≥ 3. So one is coloured 2, the other 3 and N 4 and N 5 are saturated. We then get a contradiction to Fact 5 because c(N 334 ) = c(N 344 ) = c(N 444 ) = c(N 445 ) = c(N 455 ) = 1. (f) Now consider that c(N 2 ) = c(N 5 ) = 2 and c(N 3 ) = c(N 4 ) = 3. As in Case 1e, we consider w.l.o.g. that N 44 , N 45 and N 55 are not coloured 1. Observe that N 44 and N 45 cannot be both coloured 3, otherwise I N4 (T 2 , w 2 , c) ≥ 3. i. Consider first that c(N 44 ) = c(N 45 ) = 2. Consequently, c(N 55 ) = c(N 50 ) = 3 due to the interference constraints in N 45 and N 5 . If N 00 is coloured 3, N 50 is saturated and then N 01 must be coloured 2. As a consequence, N 5 is also saturated and N 550 and N 500 must be both coloured 1. This is a contradiction as I N0 (T 2 , w 2 , c) ≥ 3. So N 00 is coloured 2 and N 5 is saturated. Thus, c(N 01 ) = 3 and N 550 and N 500 cannot receive colour 2 (interference in N 5 ) or 3 (interference in N 50 ). So, c(N 550 ) = c(N 500 ) = 1, but them I N0 (T 2 , w 2 , c) ≥ 3. ii. Either c(N 44 ) = 2 and c(N 45 ) = 3, or c(N 44 ) = 3 and c(N 45 ) = 2. In this case, observe that N 55 and N 50 can neither be both coloured 2 (interference in N 5 ) nor 3 (interference in N 4 ). So one is coloured 2, the other is coloured 3 and N 4 is saturated. If c(N 44 ) = 3 and c(N 45 ) = 2, then N 5 is also saturated and N 34 must be coloured 1. Consequently, V 0 is saturated and c(N 23 ) = c(N 33 ) = 2 and c(N 00 ) = c(N 01 ) = 3. Due to the interference in N 2 , N 12 and N 22 must be coloured 3 and then, by Fact 5, N 11 must be coloured 2. So N 2 is also saturated and then, due to the interference in N 12 , N 112 and N 122 must be both coloured 1. This is a contradiction because I N1 (T 2 , w 2 , c) ≥ 3. So c(N 44 ) = 2 and c(N 45 ) = 3. Observe that N 33 and N 34 cannot be both coloured 2, otherwise I N34 (T 2 , w 2 , c) ≥ 3. So one of them is coloured 1 and the other is coloured 2. Thus, V 0 is saturated and N 23 must be coloured 2. If c(N 33 ) = 1 and c(N 34 ) = 2, N 34 is saturated and then c(N 334 ) = c(N 344 ) = c(N 444 ) = c(N 445 ) = 1, contradicting Fact 5. So c(N 33 ) = 2 and c(N 34 ) = 1. Due to the interference in N 2 , we have that N 12 and N 22 are coloured 3 and then N 3 is also saturated. Then, N 334 must be coloured 1 due to the interference in N 3 and N 33 . If N 344 is coloured 2, N 33 is saturated and we have a contradiction to Fact 5 because c(N 223 ) = c(N 233 ) = c(N 333 ) = 1. So we get c(N 344 ) = 1 and N 34 saturated. This is a contradiction because N 333 must be coloured 2 and then I N33 (T 2 , w 2 , c) ≥ 3. Subcase c(N 2 ) = 1. W.l.o.g., let c(N 1 ) = 2. We deal with the subcases according to the colouring of N 3 , N 4 and N 5 : they are all coloured 2 (Case 2a), two of them are coloured 2 (Cases 2b and 2c), only one of them is coloured 2 (Cases 2d and 2e) or they are all coloured 3 (Case 2f). (a) Consider first the subcase c(N 3 ) = c(N 4 ) = c(N 5 ) = 2. In this case, N 4 is saturated and all the vertices N 23 , N 33 , N 34 , N 44 , N 45 , N 55 and N 50 cannot be coloured 2. Since at most one vertex in Γ 2 is coloured 1, this vertex cannot belong to the set {N 23 , N 33 , N 55 , N 50 } as it would imply a contradiction to Facts 5 in colour 3. So all the vertices in this set are coloured 3, exactly one vertex among N 34 , N 44 and N 45 is coloured 1 and V 0 is saturated. By symmetry, we can consider that N 45 is coloured 3. If N 01 is coloured 2, N 1 is also saturated and all the vertices N 11 , N 12 and N 22 must be coloured 3. This is a contradiction to Fact 5. So c(N 01 ) = 3.

  ) and we are in Case 1. Then, as N 3 and V 0 are saturated we have c(N 12 ) = c(N 22 ) = 3, implying that N 23 is saturated and so c(N 223 ) = c(N 233 ) = c(N 333 ) = c(N 334 ) = 1. However, we have that I N233 (T 2 , w 2 , c) ≥ 3. So we have that c(N 33 ) = 3. Let us now check the possible colourings of c(N 34 ). -First consider that c(N 34 ) = 1. Observe that V 0 is saturated. * If c(N 44 ) = 3, we get that c(N 45 ) = 2 and, consequently, c(N 55 ) = c(N 50 ) = 3 (otherwise, I N5 (T 2 , w 2 , c) ≥ 3). However, observe that I N4 (T 2 , w 2 , c) ≥ 3. * So c(N 44 ) = 2. If c(N 45 ) = 2, N 45 and N 5 are both saturated implying that N 55 , N 50 , N 00 and N 01 must be all coloured 3. But then we have a contradiction as I N50 (T 2 , w 2 , c) ≥ 3. So N 45 is coloured 3. N 55 and N 50 can neither be both coloured 2 (otherwise, Case 1 with N 5 ), nor 3 (otherwise, I N4 (T 2 , w 2 , c) ≥ 3). So one of these vertices is coloured 2 and the other is coloured 3. Thus, N 4 and N 5 are saturated and then N 00 and N 01 must be coloured 3 and the vertices N 445 and N 455 must be coloured 1. In case c(N 50 ) = 3, N 50 is saturated and the vertices N 555 , N 550 and N 500 must be coloured 1, contradicting Fact 5. So, we get that c(N 55 ) = 3 and c(N 50 ) = 2. Observe

N 4 and N 5

 5 are saturated. Therefore, c(N 445 ) = c(N 455 ) = 1 and we are in Case 1. (d) We now study the case c(N 3 ) = 2 and c(N 4 ) = c(N 5 ) = 3. Observe that N 45 cannot be coloured 3, otherwise we are in Case 1.

coloured 3 ,

 3 due to the interference in N 3 . * If c(N 22 ) = 3, then N 23 is saturated and c(N 12 ) = 2, implying that N 3 is also saturated. So N 223 and N 233 are both coloured 1 and N 2 is saturated. Consequently, N 122 and N 222 are both coloured 2 and we have a contradiction as I N12 (T 2 , w 2 , c) ≥ 3. * We obtain that c(N 22 ) = 2, and then N 3 is saturated and N 12 must be coloured 3. Consequently, N 223 and N 233 must be both coloured 1 (interference in N 45 ) and N 2 is also saturated. Since N 122 and N 222 cannot be both coloured 2 as we are not in Case 1, we conclude that at least one of these vertices is coloured 3 and that N 23 is saturated. But then we get that c(N 333 ) = c(N 334 ) = 1 and we have a contradiction as I N233 (T 2 , w 2 , c) ≥ 3. So we have that N 44 must be coloured 2. Let us now check the possible colourings of N 34 . -In case c(N 34 ) = 2, N 3 , N 34 and N 44 are all saturated. One of N 12 , N 22 , N 23

( a )

 a Let us consider first the case c(N 1 ) = c(N 2 ) = c(N 4 ) = c(N 5 ) = 2. In this case, N 01 , N 23 , N 34 and N 50 must be coloured 3, due to interference constraints in N 1 , N 2 , N 4 and N 5 , respectively. By symmetry, we consider that if there exists a vertex coloured 1 in Γ 2 , then it is in the set {N 33 , N 44 , N 45 , N 55 }. Thus, the vertices N 11 and N 12 must be coloured 3 and we are in Case 2 with respect to N 11 . (b) Now let c(N 1 ) = c(N 2 ) = c(N 4 ) = 2 and c(N 5 ) = 3. Observe that the vertices N 11 , N 12 and N 22 cannot be coloured 2, otherwise we would be in the previous Cases 1 or 2. If these vertices are all coloured 3, N 01 and N 23 cannot receive colour 3 as we would be in Case 2. So N 01 and N 23 must be both coloured 2 and we reach a contradiction as I N2 (T 2 , w 2 , c) ≥ 3. So one of the vertices N 11 , N 12 and N 22 is coloured 1 and V 0 is saturated. i. If c(N 11 ) = 1, N 12 and N 22 must be coloured 3. So N 23 is coloured 2 (it cannot be coloured 3 as we would be in Case 2) and then N 2 is saturated. Consequently, N 33 and N 34 are coloured 3. Observe that N 44 and N 45 can neither be both coloured 2 (Fact 4 with N 4 ) nor 3 (Fact 5). So N 4 is saturated and N 55 and N 50 are both coloured 3. Then we find a contradiction as we are in Case 1 with vertex N 5 . ii. In case N 22 is coloured 1 and c(N 11 ) = c(N 12 ) = 3, we have that N 01 is coloured 2. So N 1 is saturated, N 00 and N 50 must be coloured 3 and we are in Case 2 with N 50 . iii. So we have that c(N 12 ) = 1 and c(N 11 ) = c(N 22 ) = 3. If c(N 23 ) = 2, we have that N 2 is saturated, N 33 and N 34 must be coloured 3 and among the vertices N 44 and N 45 we have one vertex coloured 2 and the other is coloured 3. Consequently, N 55 and N 50 must be coloured 3 and we are in Case 1. So c(N 23 ) = 3.

2 . 2 .-

 22 If c(N 44 ) = 2, then c(N 33 ) = 2 and I N4 (T 2 , w 2 , c) ≥ 3, a contradiction. Thus, let c(N 44 ) = 3. In this case c(N 34 ) = 2 and c(N 33 ) = 3. Consequently, N 3 and N 4 are saturated. It implies that c(N 334 ) = c(N 344 ) = 1. As a consequence, c(N 444 ) = 3, c(N 445 ) = 1 and, since N 4 is saturated, no colour is feasible to colour N 455 . We must consider then the case in which c(N 45 ) = 3. As a consequence we have c(N 50 ) = 2. Since I N4 (T 2 , w 2 , c) ≥ 2, we conclude that c(N 44 ) = 1, c(N 34 ) = 3 and c(N 33 ) = 2. We obtain that N 3 and N 4 are saturated. Consequently, c(N 334 ) = c(N 344 ) = 1, but then N 444 has two neighbours coloured 1, a contradiction. iii. The last subcase to consider is the one in which c(N 55 ) = 3. Observe that it implies c(N 50 ) = 2 and that N 45 cannot be coloured 3. In case c(N 45 ) = 1, V 0 is saturated and then N 44 cannot be coloured 1. Suppose first that c(N 44 ) = 2.Observe that N 4 is saturated and that c(N 34 ) = 3. Consequently, no feasible colour remains to colour N 33 . Then consider that c(N 44 ) = 3. Consequently, c(N 34 ) = 2 and N 4 and N 5 are saturated. This is a contradiction as the vertices N 445 and N 455 should be both coloured 1, as they are at distance two from N 4 and N 5 , but then N 45 would have two neighbours with the same colour. Thus, c(N 45 ) = 2 and N 4 is saturated. If N 44 is coloured 1, then N 33 and N 34 should be both coloured 3, a contradiction. Consequently, c(N 44 ) = 3.In this case, we get c(N 33 ) = 3, c(N 34 ) = 1 and N 3 is saturated. However, N 334 and N 344 should be both coloured 1, a contradiction since c(N 34 ) = 1.(c) Now suppose that c(N 4 ) = 3 and c(N 5 ) = 2. First observe that c(N 01 ) = 3 and c(N 23 ) = 1, thanks to the hypothesis that no vertex has two neighbours with the same colour. By the same hypothesis, we can conclude that N 11 and N 12 cannot receive colour 2 and at most one of them is coloured 3. By the same reasoning, we can conclude that at least one of the vertices N 44 and N 45 is coloured 1. Thus, V 0 is saturated and no other vertex at distance two from V 0 can receive colour 1. Consequently, by using this information combined with the hypothesis that no vertex has two neighbours with its colour we conclude that c(N 33 ) = c(N 34 ) = 2. Thus, we conclude that c(N 44 ) = 1 and c(N 45 ) = 2. Since c(N 45 ) = c(N 5 ) = 2, we obtain that c(N 55 ) = c(N 50 ) = 3. This implies that c(N 00 ) = 2. However, I N5 (T 2 , w 2 , c) ≥ 3, thanks to the vertices N 1 , N 2 , N 00 , N 34 and N 45 . (d) Finally, if c(N 4 ) = c(N 5 ) = 3, then N 4 has two neighbours with its own colour and we are in the previous case. Suppose then that c(N 2 ) = 3. We consider the possible colourings of N 3 , N 4 and N 5 : (a) First, it is not possible to have c(N 3 ) = c(N 4 ) = c(N 5 ) = 2 as N 4 would have two neighbours with its colour. (b) Then, consider the case in which c(N 3 ) = c(N 4 ) = 2 and c(N 5 ) = 3. Once more we know that N 50 , N 00 and N 01 cannot be coloured 1, otherwise N 0 would have two neighbours with its own colour. Similarly, none of the vertices N 23 , N 33 , N 34 , N 44 and N 45 can receive colour 2, otherwise N 3 or N 4 would have two neighbours coloured 2. We prove now that no colour is feasible for N 55 . i. First, consider that c(N 55 ) = 1. Suppose also that c(N 45 ) = 1. Consequently, we get c(N 44 ) = 3, otherwise N 45 has two neighbours with colour 1. In case N 34 is coloured 1, V 0 is saturated and we reach a contradiction, because c(N 23 ) = c(N 33 ) = 3 and N 23 would have two neighbours coloured 3. Thus, suppose that c(N 34 ) = 3. It implies that c(N 33 ) = 1 and c(N 23 ) = 3. As a consequence, c(N 12 ) = c(N 22 ) = 2, because V 0 is saturated and c(N 23 ) = 3. We then get a contradiction since N 12 has two neighbours coloured 2. We conclude then that N 45 is coloured 3. Since c(N 5 ) = 3, we obtain that c(N 44 ) = 1. In case c(N 34 ) = 1, we have that V 0 is saturated and both N 23 and N 33 should be coloured 3. This would be a contradiction as N 23 would have two neighbours coloured 3. Consequently, c(N 34 ) = 3. If N 33 is coloured 1, we have c(N 23 ) = 3. Once more c(N 12 ) = c(N 22 ) = 2 and we have a contradiction as N 12 has two neighbours coloured 2. So c(N 33 ) = 3 and, consequently, c(N 23 ) = 1. Since V 0 is saturated and no vertex has two neighbours with its own colour, either we have c(N 11 ) = c(N 22 ) = 2 and c(N 12 ) = 3 or we have c(N 11 ) = c(N 22 ) = 3 and c(N 12 ) = 2. In the first case, we have a contradiction as I N1 (T 2 , w 2 , c) ≥ 3 and in the latter case we also have a contradiction as I N2 (T 2 , w 2 , c) ≥ 3 (recall that c(N 50 ) = 2 and in the set {N 00 , N 01 } we have one vertex coloured 2 and the other coloured 3). ii. Suppose then that c(N 55 ) = 2. We distinguish three cases. c(N 44 ) = c(N 45 ) = 1, we have that c(N 34 ) = 3. In case c(N 33 ) = 1, we have that c(N 23 ) = 3 and V 0 is saturated. This is a contradiction as N 12 and N 22 have no feasible colouring. Then consider the case c(N 33 ) = 3. Observe that c(N 344 ) = 2, otherwise N 34 or N 44 have two neighbours with their colour. Consequently, N 4 is saturated and all the vertices N 444 , N 445 and N 455 should be coloured 3, as they all have two adjacent neighbours coloured 1 and they are all at distance two from N 4 . This is a contradiction as N 455 would have two neighbours with its own colour. c(N 45 ) = 1 and c(N 44 ) = 3. Suppose that c(N 33 ) = c(N 34 ) = 1. Thus, V 0 is saturated and c(N 23 ) = 3. Once more we get a contradiction as N 12 and N 22 should be both coloured 2. Thus, consider now that c(N 33 ) = 3 and c(N 34 ) = 1. Observe that c(N 23 ) = 1 and V 0 is saturated. If c(N 22 ) = 2, we get that c(N 12 ) = 3 and c(N 11 ) = 2. Since at least one of the vertices N 50 and N 00 must be coloured 2, we reach a contradiction as I N1 (T 2 , w 2 , c) ≥ 3. In case c(N 22 ) = 3, we get that c(N 12 ) = 2 and c(N 11 ) = 3. Since N 2 is saturated, we conclude that c(N 01 ) = 2. Once more we obtain a contradiction as I N1 (T 2 , w 2 , c) ≥ 3. Let us now study the case c(N 33 ) = 1 and c(N 34 ) = 3. In case c(N 50 ) = 2, N 4 is saturated and we obtain a contradiction as all the vertices N 334 , N 344 and N 444 should be coloured 1. Thus, consider that c(N 50 ) = 3. In this case, N 5 is saturated and we get a contradiction as N 00 and N 01 should be both coloured 2. Since we do not have the case c(N 33 ) = 3 and c(N 34 ) = 3 as N 34 would have two neighbours with its colour, we conclude that c(N 45 ) = 3. So c(N 45 ) = 3, then we get that c(N 44 ) = 1 (otherwise N 45 has two neighbours of the same colour), c(N 50 ) = 2 and c(N 00 ) = 3. In this case, we easily obtain a contradiction as N 4 is saturated and the vertices N 445 and N 455 have no feasible colouring. iii. We conclude that c(N 55 ) = 3. As a consequence, we get c(N 45 ) = 1 and c(N 50 ) = 2. If c(N 44 ) = 1, then c(N 455 ) = 2 and N 4 is saturated. But then all the vertices N 34 , N 344 , N 444 and N 445 should be coloured 3. This would be a contradiction. Consequently, c(N 44 ) = 3. In this case, in the set {N 00 , N 01 } there is exactly one vertex coloured 2 and the other is coloured 3, thanks to the interference constraint in vertex N 5 and to the hypothesis that no vertex has two neighbours with its own colour. Similarly, we can conclude that in the set {N 445 , N 455 } there is exactly one vertex coloured 1 and the other is coloured 2. Since N 5 is saturated, we get c(N 34 ) = 1. So, N 45 is saturated and both vertices N 555 and N 550 should be coloured 2. This would be a contradiction as N 550 would have two neighbours coloured 2. (c) Now let c(N 3 ) = c(N 5 ) = 2 and c(N 4 ) = 3. We show now that no colour is feasible to N 55 . i. Suppose first that c(N 55 ) = 1. First consider that c(N 45 ) = 1. Then N 44 cannot be coloured 1 because we would have I N45 (T 2 , w 2 , c) ≥ 3. -Then, suppose that N 44 is coloured 2 and N 34 is coloured 1. Since V 0 is saturated, all the remaining vertices in Γ 2 are not coloured 1. In case N 33 is coloured 2, we have that N 3 is saturated and thus c(N 22 ) = c(N 23 ) = 3. This is a contradiction to the hypothesis that no vertex has two neighbours with its colour as c(N 2 ) = 3. In case N 33 is coloured 3, we have that c(N 23 ) = 2, then c(N 22 ) = 3 and c(N 12 ) = 2. But then, I N3 (T 2 , w 2 , c) ≥ 3, a contradiction. -Consequently, if N 44 is coloured 2, N 34 must be coloured 3 (observe it cannot be coloured 2 as it would have two neighbours N 3 and N 44 coloured 2). If N 50 is coloured 2, N 5 is saturated and the vertices N 445 , N 455 and N 555 should be all coloured 3 (as N 45 and N 55 are both coloured 1). This is a contradiction as N 455 has two neighbours with its own colour. Consequently, we have c(N 50 ) = 3. Observe that among the vertices N 445 and N 455 at least one of them is coloured 3. Thus, N 4 is saturated and in the set {N 23 , N 33 } we have exactly one vertex coloured 1 (due to the interference constraint in V 0 ) and the other is coloured 2. Since V 0 and N 3 are saturated, the vertices N 12 and N 22 should be both coloured 3. This is a contradiction as c(N 2 ) = 3. -Thus, c(N 44 ) = 3 and N 34 can be either coloured 1 or 2. If c(N 34 ) = 1, we get that V 0 is saturated. If N 33 is coloured 2, N 23 is necessarily coloured 3 and N 12 and N 22 should be both coloured 2. This is a contradiction as N 12 would have two neighbours coloured 2. Thus N 33 is coloured 3. It implies that c(N 23 ) = 2, then c(N 22 ) = 3, c(N 12 ) = 2 and c(N 01 ) = c(N 11 ) = 3. This is a contradiction as I N2 (T 2 , w 2 , c) ≥ 3. -We conclude that c(N 44 ) = 3 and c(N 34 ) = 2. Observe that c(N 344 ) = 1 and c(N 445 ) = 2, thanks to the hypothesis that no vertex has two neighbours with its colour. Since we get that N 45 is saturated, we have c(N 444 ) = 2 and, consequently, c(N 455 ) = 3. Observe now that N 34 and N 4 are saturated (because among N 33 and N 334 we have exactly one vertex coloured 1 and the other is coloured 3). As a consequence, c(N 23 ) = 1 and c(N 50 ) = 2. At this point the colours of the remaining vertices in Γ 2 are fixed as V 0 is saturated. We have c(N 00 ) = c(N 01 ) = c(N 12 ) = 3 and c(N 11 ) = c(N 22 ) = 2. Thus we observe that I N1 (T 2 , w 2 , c) ≥ 3, a contradiction. Then, consider now that N 45 is coloured 2. It implies that c(N 50 ) = 3 and that among N 00 and N 01 we have exactly one vertex coloured 2 and the other is coloured 3. Consequently, N 5 is saturated and among N 555 and N 550 we have exactly one vertex coloured 1 and one vertex coloured 3. In case N 44 is coloured 1, N 55 is saturated. Thus, N 445 , N 455 and N 500 are all coloured 3. This is a contradiction as I N50 (T 2 , w 2 , c) ≥ 3. If c(N 44 ) = 3, we obtain that c(N 445 ) = 1 and that c(N 455 ) = 3. Consequently, N 55 is saturated and c(N 500 ) = 3. Once more we have a contradiction as I N50 (T 2 , w 2 , c) ≥ 3. Suppose then that c(N 45 ) = 3. If c(N 50 ) = 2, we have that c(N 00 ) = 3. Since I N5 (T 2 , w 2 , c) ≥ 2 and c(N 4 ) = c(N 45 ) = 3, we conclude that among N 34 , N 44 and N 445 we have exactly two vertices coloured 1 and the other is coloured 2. Consequently, we get N 5 is saturated and thus c(N 01 ) = 3. This implies that c(N 500 ) = 1 and then N 55 is saturated. Thus, we get a contradiction as we have no feasible colouring for the vertices N 455 and N 555 . -So c(N 50 ) = 3. If c(N 34 ) = c(N 44 ) = 1, we observe that V 0 is saturated and that among N 23 and N 33 we have exactly one vertex coloured 2 and one coloured 3. Consequently, N 4 is saturated and we reach a contradiction as no colouring is feasible to the vertices N 334 , N 344 and N 444 .

  w 2 , c) ≥ 3. In case c(N 44 ) = 1 and c(N 45 ) = 3, no colouring is feasible to the vertices N 445 and N 455 . If c(N 44 ) = 3 and c(N 45 ) = 1, observe that c(N 34 ) = c(N 445 ) = 1 and that one vertex among N 555 and N 550 is coloured 1. Thus, I N45 (T 2 , w 2 , c) ≥ 3, a contradiction.iii. We then conclude that the only possible colour for N 55 is the colour 3. Recall N 50 cannot be coloured 1 as N 0 would have two neighbours with its own colour.Let us first consider the case in which c(N 50 ) = 2. As a consequence, we obtain c(N 00 ) = 3 and c(N 45 ) = 1.

Consequently, c(N 11 )

 11 = 2 and N 1 is saturated. In this case, no colouring is feasible for the vertices N 122 , N 22 and N 23 and we complete the proof of this case as no colour is feasible for the vertex N 55 . (d) In case we have c(N 3 ) = 2 and c(N 4 ) = c(N 5 ) = 3, we are in a symmetric case to 1b. (e) If c(N 3 ) = 3 and c(N 4 ) = c(N 5 ) = 2, we obtain a symmetric case to 1c. (f) The case c(N 3 ) = c(N 5 ) = 3 and c(N 4 ) = 2 is symmetric to 2a. (g) Finally, it is not possible to have c(N 3 ) = c(N 4 ) = 3 as N 3 would have two neighbours, N 2 and N 4 , with its own colour.

( a )

 a The three other neighbours of V 0 coloured 2 are consecutive and let them be N 0 , N 1 and N 2 . N 34 , N 44 and N 45 are all coloured 2, otherwise N 4 would have four neighbours coloured 1 and we would be in Case 1. At most one of N 01 , N 11 and N 12 has colour 2, otherwise N 1 would have four neighbours coloured 2 and we would be again in Case 1. i.N 11 is coloured 2. Then c(N 01 ) = c(N 12 ) = 1. As already I V0 (T 2 , w 2 , c) ≥ 4,there is at most another vertex in Γ 2 coloured 1. So either the three vertices N 22 , N 23 and N 33 or the three vertices N 00 , N 50 and N 55 are all coloured 2 and then I N2 (T 2 , w 2 , c) ≥ 5 or I N5 (T 2 , w 2 , c) ≥ 5, a contradiction.RR n°7590ii. N 01 is coloured 2 (the case N 12 is symmetric). Then, c(N 11 ) = c(N 12 ) = 1. One of N 00 and N 50 is of colour 1 otherwise, N 0 has four neighbours of colour 2. But then I V0 (T 2 , w 2 , c) ≥ 4.5 so all the other vertices of Γ 2 are coloured 2. Therefore, I N2 (T 2 , w 2 , c) ≥ 5, a contradiction. iii. N 01 , N 11 and N 12 all have colour 1. In that case I V0 (T 2 , w 2 , c) ≥ 4.5. Therefore all the other vertices of Γ 2 are coloured 2 and I N0 (T 2 , w 2 , c) ≥ 4.5. So the other vertices at distance two of N 0 are coloured 1 and then I N01 (T 2 , w 2 , c) ≥ 5, a contradiction.(b) Among the three vertices of colour

  {u∈V |uv∈E and c(v)=x} w(u, v)

Figure 9 :

 9 Figure 9: Results comparison for Levelling heuristic, Branch-and-Bound algorithm and Integer Linear Programming Formulation.

  N 11 is coloured 2, then N 33 and N 34 are not coloured 2, otherwise I

N2 (T 2 , w 2 , c) > 1 and we have a sequence of five vertices N 12 , N 22 , N 23 , N 33 and N 34 contradicting Fact 2 as four are of colour 4 (indeed, at most one is coloured 3 due to interference in colour 3 with N 3 or N 22 ). So N 11 is coloured 3 or 4. If N 1 also is coloured 3 or 4, we have a contradiction with Fact 2 applied to the five vertices N 00 , N 01 , N 11 , N 12 and N 22 , by the same previous argument. So c(N 1 ) = 1; furthermore N 4 is not coloured 1 (at most one neighbour coloured 1), nor 2 as we have seen above, nor 3, otherwise we are in the case

  [START_REF] Araujo | Weighted Improper Colouring[END_REF]. Consequently, as N 23 and N 33 are saturated, we reach a contradiction to Fact 5 as all the vertices N 222 , N 223 , N 233 , N 333 and N 334 must be coloured 1. Thus, N 44 is coloured 3 (it cannot be coloured 2 due to Fact 5). In case N 33 is coloured 1, we have that V 0 is saturated and all the vertices N 23 , N 34 and N 45 are coloured 3. As N 34 is saturated, the vertices N 233 , N 333 and N 334 must be coloured 1. This contradicts Fact 3. Consequently, N 33 is coloured 3. N 34 cannot be coloured 3, because it would imply that c(N 45 ) = 1 and, consequently, V 0 is saturated and the vertices N 22 and N 23 should be coloured 3 and we would have a contradiction to Fact 5. Thus, N 34 is coloured 1. Consequently, N 22 , N 23 and N 45 are coloured 3. The vertices N 334 and N 344 must then be coloured 1 due to the interference constraints on the vertices N 3 , N 33 and N 44 . However, we reach a contradiction as no colour is feasible to vertex N 233 (and N 333 ). ii. So we conclude that c(N 12 ) = 3.

  In case N 44 is coloured 2, then N 4 is saturated and the vertices N 45 , N 55 and N 50 are coloured 3, contradicting Fact 3. Thus, c(N 44 ) = 3.-If N 45 is coloured 2, N 3 and N 4 are saturated and then, N 55 and N 50 are coloured 3 and it implies that N 5 is saturated. Consequently, N 34 is coloured 1 and N 23 and N 33 are coloured 3. Thus, N 23 is saturated and the vertices N 223 , N 233 , N 333 and N 334 are coloured 1, contradicting Fact 5. -Thus, N 45 is also coloured 3 and we obtain c(N 55 ) = 2. N 23 cannot be coloured 1, otherwise N 33 and N 34 being coloured 3, we would contradict Fact 5. If N 34 is coloured 3, N 44 is saturated and then N 50 must be coloured 2 and N 4 is saturated. In this case, we get a contradiction to Fact 5 because all the vertices N 334 , N 344 , N 444 and N 445 must be coloured 1. N 01 is coloured 3 and then N 50 must be coloured 2, due to the interference constraint in N 5 . Consequently, N 4 is saturated and all the vertices N 344 , N 444 , N 445 and N 455 must be coloured 1, due to the interference constraints in N 4 , N 44 and N 45 . This contradicts Fact 5. (c) Let us consider now the case c(N 2 ) = c(N 3 ) = c(N 5 ) = 2 and c(N 4 ) = 3.Recall that N 12 , N 11 , N 01 , N 00 and N 50 cannot be coloured 1. i. Let us study the case c(N 12 ) = 2. In this case, N 2 is saturated and thus N 01and N 11 must be coloured 3.In case N 34 is coloured 1, the vertices N 22 , N 23 and N 33 must be coloured 3 as V 0 and N 2 are saturated. Consequently, N 23 is also saturated. It implies that the vertices N 122 , N 222 , N 223 and N 233 must be all coloured 1. By Fact 5, we conclude that N 333 must be coloured 2 and then N 3 is also saturated. Then consider that N 12 is coloured 3. We claim that neither N 22 nor N 23 can receive colour 2. For otherwise, suppose the case where at least one of these vertices would be coloured 2. As N 2 would be saturated, the vertices N 01 and N 11 should be both coloured 3. This would imply that N 112 and N 122 should be coloured 1 and 3, respectively, due to Fact 3 and the interference constraint in N 1 and N 2 . Consequently, as N 1 and N 12 would be both saturated, N 22 and N 23 should be both coloured 2, a contradiction to Fact 3. Observe that N 22 and N 23 cannot be both coloured 1 due to the interference in V 0 . Let us study the three remaining cases: c(N 22 ) = 1 and c(N 23 ) = 3. At most one of the vertices N 33 and N 34 is coloured 2, due to Fact 3. If exactly one of them is coloured 2 (and thus the other is coloured 3 thanks to the interference in V 0 ), as N 3 is saturated, N 44 and N 45 must be coloured 3. This is a contradiction as I N4 (T 2 , w 2 , c) ≥ 3. Thus, N 33 and N 34 are both coloured 3 and it implies that N 44 and N 45 are both coloured 2, because of Facts 3 and 5. As N 45 is saturated, N 55 and N 50 are both coloured 3 and we reach a contradiction as I N4 (T 2 , w

2

, w 2 , c) ≥ 3. We then conclude that c(N 22 ) = 3. Due to Facts 3 and 5, at least one of the vertices N 23 , N 33 and N 34 is coloured 1 and the two others are coloured 3. Consequently, V 0 is saturated. So c(N 23 ) = c(N 33 ) = 3, c(N 34 ) = 1 and c(N 11 ) = 2. If N 01 is coloured 2, we have that N 2 is saturated and, since N 22 is saturated, we have that the vertices N 112 , N 122 , N 222 , N 223 and N 233 must be all coloured 1, contradicting Fact 5. Thus, Consequently, c(N 44 ) = c(N 45 ) = 3, but then N 4 has interference at least 3, a contradiction. Thus we conclude that N 34 is coloured 3, as it cannot be coloured 2 thanks to the interference constraint on N 2 . Observe that none of the vertices N 44 and N 45 can be coloured 1, as it would imply that V 0 is saturated and that the vertices N 22 , N 23 and N 33 should be all coloured 3, leading to a contradiction to Fact 5. N 44 and N 45 can neither be both coloured 2 nor 3, due to interference constraints in N 3 and N 4 , respectively. In case c(N 44 ) = 2 and c(N 45 ) = 3, observe that among N 23 and N 33 we have one vertex coloured 1 and the other is coloured 3. Consequently, V 0 and N 4 are both saturated and N 55 and N 50 must be coloured 2. But then I N5 (T 2 , w 2 , c) ≥ 3, a contradiction. In case c(N 44 ) = 3 and c(N 45 ) = 2, we conclude that N 33 is coloured 1, thanks to Fact 3, and thus V 0 is saturated; consequently, c(N 23 ) = 3 and N 4 is saturated, but then c(N 55 ) = c(N 50 ) = 2 and I N5 (T 2 , w 2 , c) ≥ 3. ii.

  [START_REF] Araujo | Weighted Improper Colouring[END_REF] is also saturated and N 44 and N 45 must be both coloured 3. Then N 4 is saturated and N 55 and N 50 are both coloured 2. This is a contradiction as I N5 (T 2 , w 2 , c) ≥ 3. Thus we know that c(N 34 ) = 3. In case N 44 is coloured 3, N 4 is saturated and N 45 , N 55 and N 50 should be all coloured 2. This contradicts Fact 3.

Then c(N 44 ) = 2. So N 44 is coloured 2 and we know that N 23 is saturated. Then, among N 233 , N 333 and N 334 there is exactly one vertex coloured 2, due to Fact 3 and to the interference in N 3 . As N 3 is saturated, we conclude that c(N 45 ) = 3. But N 4 is saturated, N 55 and N 50 must be coloured 2 and we find a contradiction as I N5 (T 2 , w 2 , c) ≥ 3.

  [START_REF] Aardal | Models and solution techniques for frequency assignment problems[END_REF]. Suppose that at one of the vertices N 23 or N 33 is coloured 2. Then, N 3 is saturated and the vertices N 12 , N 22 and N 45 must be all coloured 3. So N 55 is coloured 2, as we are no longer in Case 1, and it implies that N 4 is saturated. As a consequence, N 50 is coloured 3 and N 5 is also saturated. Thus, N 00 and N 01 must be coloured 2, N 1 is saturated and N 11 is coloured 3. Observe that N 112 and N 122 are both coloured 1, otherwise we are in Case 1. So N 2 is also saturated and no feasible colour remains to colour N 223 . So N 23 and N 33 are both coloured 3.-If N 22 is coloured 3, N 12 is coloured 2 (Fact 5), N 11 is coloured 3 (as we are not in Case 1) and N 01 is also coloured 3 (interference in V 0 and N 1 ). If c(N 00 ) = 3, N 01 is saturated and then N 50 is coloured 2. It implies that N 1 is saturated and N 001 and N 011 must be both coloured 1. Consequently, N 0 is saturated and N 000 and N 500 are both coloured 2. Thus, N 50 is also saturated and the vertices N 45 and N 55 should be both coloured 3. But then we are in Case 1. So N 00 is coloured 2 and N 1 is saturated. Consequently, N 50 is coloured 3 and N 55 must be coloured 2 as we are no longer in Case 1. But then no feasible colour remains to colour N 45 . -Thus, we have c(N 22 ) = 2. If N 12 is coloured 2, N 1 is saturated and we have a contradiction to Fact 5, because all the vertices N 50 , N 00 , N 01 and N 11 must be coloured 3. So, we conclude that c(N 12 ) = 3. If N 01 or N 11 are coloured 2, N 1 is saturated and N 50 and N 00 must be coloured 3. In this case, N 45 and N 55 cannot receive colour 3, due to the interference in N 5 . So they are both coloured 2 and we reach a contradiction as I N4 (T 2 , w 2 , c) ≥ 3. Consequently, N 01 and N 11 are both coloured 3. Observe that N 45 is also coloured 3, otherwise N 4 is saturated, N 50 and N 00 are coloured 3 and we are in Case 1. Consequently, N 55 and N 50 are coloured 2, as we are no longer in Case 1 and we cannot violate the interference constraint in N 5 . Moreover, N 00 is also coloured 2, otherwise I N01 (T 2 , w 2 , c) ≥ 3. But then we have a contradiction as I N50 (T 2 , w 2 , c) ≥ 3. iii. We conclude that N 44 must be coloured 3. Recall that N 34 cannot be coloured 2 as we would be in Case 1. Consider first the case in which c(N 34 ) = 1 and thus V 0 is saturated. If N 45 is coloured 2, N 4 is saturated and N 50 and N 00 should be both coloured 3. But then we are in Case 1. So N 45 is coloured 3 and N 55 must be coloured 2.Observe that N 23 and N 33 cannot be both coloured 2, due to Fact 3. In case one of these vertices is coloured 2 and the other is coloured 3, observe that N 3 and N 4 are saturated. Consequently, N 50 is coloured 3 and N 45 and N 5 are also saturated. We then reach a contradiction to Fact 5 as all the vertices N 344 , N 444 , N 445 and N 455 must be coloured 1. So we conclude that N 23 and N 33 must be both coloured 3.If N 50 is coloured 3, N 5 is saturated. Then, N 00 and N 01 must be coloured 2, then N 1 is saturated and we reach a contradiction to Fact 5 as N 11 , N 12 and N 22 must be all coloured 3. So N 50 is coloured 2 and N 4 is saturated. Consequently, N 344 and N 444 are both coloured 1, due to the interference constraints in N 4 and N 44 . Thus, N 34 is also saturated and N 445 must be coloured 3. But then we are in Case 1.We deduce that c(N 34 ) = 3. We now study the possible colourings of N 45 . -If c(N 45 ) = 2, N 4 is saturated. The interference constraints in V 0 and N 5 lead us to the conclusion that among N 55 and N 50 we have one vertex coloured 1 and the other is coloured 3. Consequently, V 0 is saturated and N 23 and N 33 are both coloured 3. This is a contradiction asI N34 (T 2 , w 2 , c) ≥ 3. -Now consider that c(N 45 ) = 1 (V 0 is saturated). Thevertices N 23 and N 33 cannot be both coloured 2, due to Fact 3. They cannot also be both coloured 3, because of the interference constraint in N 34 . So among N 23 and N 33 we have one vertex coloured 2 and the other is coloured 3 and N 3 is saturated. The vertices N 55 and N 50 can neither be both coloured 2, because of the interference in N 4 , nor 3, as we are not in Case 1. So one of them is coloured 2 and the other is coloured 3. Thus, N 4 is also saturated. Similarly, we can conclude that among N 444 and N 445 we have one vertex coloured 1 and the other is coloured 3 (recall that these vertices cannot receive colour 2 as N 4 is saturated). Consequently, N 44 is saturated and the vertices N 344 and N 455 must be coloured 1. This is a contradiction as I N45 (T 2 , w 2 , c) ≥ 3. -So we have c(N 45 ) = 3. Consequently, N 33 , N 55 and N 50 cannot receive colour 3. We thus conclude that two of these vertices are coloured 2 and the other is coloured 1, by considering the interference in V 0 and N 4 . We then obtain that N 334 , N 344 , N 444 , N 445 and N 455 are all coloured 1. This contradicts Fact 5. (c) We now treat the case c(N 3 ) = c(N 5 ) = 2 and c(N 4 ) = 3. Let us consider the possible colours of N 23 . i. Suppose first that N 23 is coloured 1. In this case, V 0 and N 2 are saturated. In case N 33 is coloured 2, N 34 must be coloured 3 and N 44 must be coloured 2, otherwise we would be in Case 1. So N 3 is also saturated and N 45 must be coloured 3. Since N 2 and N 3 are both saturated, N 12 , N 22 , N 223 and N 233 must be all coloured 3 and then N 22 is saturated. It implies that N 11 , N 112 , N 122 are coloured 2 and then we reach a contradiction as I N1 (T 2 , w 2 , c) ≥ 3. We conclude that N 33 must be coloured 3. Observe that N 44 and N 45 cannot be both coloured 3, as we are no longer in Case 1. Thus, at least one of these vertices is coloured 2. If N 34 is coloured 2, N 3 is saturated. Then, the vertices N 12 , N 22 , N 223 and N 233 must be all coloured 3. This contradicts Fact 5. Consequently, N 34 is coloured 3 and N 44 must be coloured 2, otherwise we would be in Case 1. Observe that N 45 cannot be coloured 2, because, otherwise N 5 will be saturated, c(N 55 ) = c(N 50 ) = c(N 00 ) = c(N 01 ) = 3 and I N50 (T 2 , w 2 , c) ≥ 3. So N 45 is coloured 3, N 4 is saturated and N 55 and N 50 are both coloured 2. However, we are in Case 1 with N 5 . ii. Now consider that c(N 23 ) = 2. Observe that neither N 33 nor N 34 are coloured 2 due to the interference in N 3 . Suppose first that c(N 33 ) = 1. It implies that V 0 is saturated and that N 34 is coloured 3. Consequently, N 44 must be coloured 2, otherwise we are in Case 1, and then N 3 is saturated. So, N 12 , N 22 and N 45 are coloured 3. Observe that among N 55 and N 50 , we must have one vertex coloured 2 and the other must be coloured 3 (due to Fact 5 and to the hypothesis that we are not in Case 1). So N 4 is also saturated and it implies that N 334 and N 344 are coloured 1. We conclude that N 33 is saturated and that the vertices N 223 , N 233 and N 333 should be all coloured 3. This contradicts Fact 5. Now consider the case in which c(N 33 ) = 3 and c(N 34 ) = 1. So V 0 is saturated and we can see that N 44 and N 45 can neither be both coloured 2 (interference in N 3 ) nor 3 (Case 1 with N 4 ). Thus, one is coloured 2 and the other is coloured 3. Consequently, N 3 is saturated and N 12 and N 22 are both coloured 3. Furthermore, both N 334 and N 344 cannot be coloured 1 (Case 1 with N 34 ). One of them at least is coloured 3. Then N 55 and N 50 can neither be both coloured 2 (Case 1 with N 5 ) nor 3 (otherwise I N4 (T 2 , w 2 , c) ≥ 3). So among N 55 and N 50 we have one vertex coloured 2 and the other is coloured 3. We conclude that N 5 is saturated, N 00 and N 01 are coloured 3 and, due to Fact 5, N 11 is coloured 2. It implies that N 1 is saturated and N 122 must be coloured 1 (it cannot be coloured 3, otherwise we would be in Case 1 with N 12 ). So N 2 is also saturated and N 223 and N 233 must be both coloured 3. This contradicts Fact 5. We obtain that N 33 and N 34 are both coloured 3. Consequently, N 44 cannot be coloured 3 (Fact 3 with N 34 ). -Suppose first that N 44 is coloured 1. If c(N 45 ) = 3, N 4 is saturated and we are in Case 1 with N 5 instead of V 0 , because N 55 and N 50 must be both coloured 2. So N 45 is coloured 2 and it implies that N 55 and N 50 must be both coloured 3, due to the interference constraint in V 0 and N 5 . Thus, N 4 is saturated. Since N 3 is also saturated, we get that N 334 and N 344 are both coloured 1. The vertices N 444 and N 445 can neither receive colour 1, due to the interference in N 44 , nor colour 3, since N 4 is saturated. Thus, they are both coloured 2. But then we have a contradiction as I N45 (T 2 , w 2 , c) ≥ 3. -So we get that c(N 44 ) = 2 and then N 3 is saturated. Neither N 12 , nor N 22 can be coloured 1, otherwise N 2 would also be saturated and it would imply that N 223 and N 233 should be coloured 3, leading to a contradiction to Fact 5. So we get that c(N 12 ) = c(N 22 ) = 3. Consequently, c(N 233 ) = c(N 333 ) = c(N 334 ) = c(N 344 ) = 1, due to interference constraints in N 3 , N 33 and N 34 . So c(N 223 ) = 3 and N 33 is also saturated. It implies that N 22 is saturated and then N 11 can either be coloured 1 or 2. In case it is coloured 1, N 2 is saturated, N 112 , N 122 and N 222 must be coloured 2 and we have a contradiction as I N122 (T 2 , w 2 , c) ≥ 3. If N 11 is coloured 2, N 1 is saturated and then N 112 and N 122 must be coloured 1. However, we get that I N2 (T 2 , w 2 , c) ≥ 3. iii. We conclude that N 23 is coloured 3. Suppose first that c(N 33 ) = 1. Consequently, V 0 is saturated. -Let us first consider the subcase in which N 34 is coloured 2. Then, N 44 and N 45 can neither be both coloured 2, due to the interference in N N 4 is saturated implying N 334 and N 344 must be both coloured 1. But then N 33 is also saturated, N 22 and N 223 are be both coloured 3 and we are in Case 1 with vertex N 23 . -We conclude that c(N 34 ) = 3. Since we are no longer in Case 1, we get that c(N 44 ) = 2. N 45 and N 55 can neither be both coloured 2 (Fact 3 with N 45 ), nor 3 (interference in N 4 ). So one of these vertices is coloured 2 and the other is coloured 3, implying that N 5 is saturated and then that c(N 50 ) = c(N 00 ) = c(N 01 ) = 3. However, we get a contradiction as neither N 45 is coloured 3, otherwise I N4 (T 2 , w 2 , c) ≥ 3, nor N 55 is coloured 3, otherwise I N50 (T 2 , w 2 , c) ≥ 3. Let us consider now the case c(N 33 ) = 2. Observe that N 34 cannot be also coloured 2, due to the interference constraint in N 3 . -In case c(N 34 ) = 1, we have that V 0 is saturated and then N 44 and N 45 can neither be both coloured 2 (interference in N 3 ) nor 3 (Case 1 with N 4 ). So among N 44 and N 45 we find one vertex coloured 2 and the other is necessarily coloured 3. Consequently, N 3 is saturated, N 12 and N 22 are coloured 3 and then N 223 must be coloured 1. So N 2 is also saturated and N 233 must be coloured 3. This is a contradiction as I N23 (T 2 , w 2 , c) ≥ 3. -We conclude that N 34 must be coloured 3. Consequently, N 44 cannot be coloured 3, as we are not in Case 1. Let us check the possible colourings of N 44 .

[START_REF] Araujo | Weighted Improper Colouring[END_REF]

, nor 3, since we are no longer in Case 1. So among N 44 and N 45 we have one vertex coloured 2 and the other is coloured 3. It implies that N 3 is saturated. Due to the interference in V 0 and N 5 , we conclude that c(N 55 ) = c(N 50 ) = 3. So If N 44 is coloured 1, V 0 is saturated. Then, if N 45 is coloured 3, N 4 is saturated and N 55 and N 50 are forced to be coloured 2. But then we are in Case 1 with N 5 . So N 45 is coloured 2, N 3 is saturated and the vertices N 55 and N 50 must be coloured 3, due to the interference in N 5 . As a consequence, N 4 is also saturated and the vertices N 334 and N 344 must be coloured 1. As we are no longer in Case 1, N 444 must be coloured 2. Due to the interference constraints in N 4 and N 45 , we get that N 445 and N 455 must be both coloured 1. This is a contradiction to Fact 5. So N 44 must be coloured 2 and then N 3 is saturated. Observe that exactly one of the vertices N 45 , N 55 and N 50 must be coloured 1, otherwise N 45 must be coloured 3 (interference in N 3 ) and N 55 and N 50 must be coloured 2 (interference in N 4

  that N 555 and N 550 can neither receive colour 2 (since N 5 is saturated) nor 3 (otherwise, I N55 (T 2 , w 2 , c) ≥ 3). Thus, they are both coloured 1 and, consequently, N 500 is coloured 3. It implies that N 00 is saturated and then we get that N 11 must be coloured 2. As a consequence, N 1 is saturated and N 12 and N 22 are both coloured 3. However, we get that I N23 (T 2 , w 2 , c) ≥ 3.-Now consider that c(N 34 ) = 2. Let us check the possible colourings of N 44 . * First suppose that c(N 44 ) = 1. If N 45 is coloured 2, then N 3 is saturated and we have that N 12 and N 22 are coloured 3. This is a contradiction asI N23 (T 2 , w 2 , c) ≥ 3.So N 45 is coloured 3. The vertices N 55 and N 50 can neither be both coloured 2 (otherwise, Case 1 with N 5 ) nor 3 (otherwise, I N4 (T 2 , w 2 , c) ≥ 3). So one is coloured 2 and the other is coloured 3. As a consequence, N 4 and N 5 are both saturated implying that N 445 and N 455 are coloured 1 and then that N 444 is coloured 2. But then N 334 and N 344 must be both coloured 1 (interference in N 34 ) and we have a contradiction to Fact 5. * Now let c(N 44 ) = 2. Observe that N 3 and N 34 are saturated and that N 12and N 22 cannot be both coloured 3, otherwise I So we conclude that N 33 and N 34 are both coloured 3 and both saturated. If the vertices N 12 , N 44 and N 45 are not coloured 1, they must be all coloured 2 and we have that N 3 is saturated and so c(N 223 ) = c(N 233 ) = c(N 333 ) = c(N 334 ) = c(N 344 ) = 1,contradicting Fact 5. So one of these vertices is coloured 1 and V 0 is saturated. In case N 12 is coloured 1, N 44 and N 45 must be coloured 2 and N 45 is saturated. Consequently, N 55 and N 50 are coloured 3 and we have a contradiction as I N4 (T 2 , w 2 , c) ≥ 3. Then, either N 44 or N 45 is coloured 1 (the other being coloured 2) and N 12 is coloured 2. If N 44 is coloured 1, then N 55 and N 50 are not coloured 2, otherwise I N5 (T 2 , w 2 , c) ≥ 3. So they are both coloured 3, but then I N4 (T 2 , w 2 , c) ≥ 3. So we have that N 44 is coloured 2 and N 45 is coloured 1. Consequently, N 55

N23 (T 2 , w 2 , c) ≥ 3. So among N 12 and N 22 we have one vertex coloured 1 and the other is coloured 3. It implies that V 0 is saturated. Observe also that the vertices N 45 , N 55 and N 50 cannot receive colour 2 due to the interference constraint in N 5 . Then, we have a contradiction as N 45 , N 55 and N 50 are all coloured 3 and we get

I N4 (T 2 , w 2 , c) ≥ 3. * We conclude that c(N 44 ) = 3. If c(N 45 ) = 1, V 0 is saturated. In this case,

N 55 and N 50 can neither be both coloured 2 (otherwise, Case 1 with N 5 ) nor 3 (otherwise, I N4 (T 2 , w 2 , c) ≥ 3). So one of these vertices is coloured 2, the other is coloured 3 and we get that N 4 and N 5 are saturated. Thus, N 445 and N 455 must be coloured 1 and we are in Case 1 for N 45 . N 45 cannot be coloured 3 as we are no longer in Case 1, so its colour is 2 and N 3 and N 5 are both saturated. N 55 and N 50 cannot be both coloured 3, otherwise I N4 (T 2 , w 2 , c) ≥ 3. So one of these vertices is coloured 1 implying that V 0 is saturated. Consequently, N 12 and N 22 are both coloured 3 and we get a contradiction as I N23 (T 2 , w 2 , c) ≥ 3. and N 50 can neither be both coloured 2 (interference in N 5 ) nor 3 (interference in N 4 ). So one is coloured 2 and the other is coloured 3 implying that

  ). If N 55 is coloured 3, N 50 must be coloured 2 and we are in Case 2b with central vertex N 5 . So N 55 is coloured 2. In case N 44 is coloured 3, N 34 must be coloured 2 and then N 33 must be coloured 3, because we are not in Case 1. Thus, N 4 is saturated, N 23 and N 50 must be coloured 2 and N 3 is also saturated. Consequently, N 334 and N 344 are both coloured 1. If N 00 is coloured 2, N 50 is saturated and then N 455 must be coloured 1, N 45 is also saturated and N 01 is coloured 3. Since N 555 and N 550 must be both coloured 3, we reach a contradiction as I N5 (T 2 , w 2 , c) ≥ 3. So we conclude that c(N 00 ) = 3. Recall that N 3 is saturated and thus, N 12 and N 22 must be both coloured 3. N 01 and N 11 can neither be both coloured 2 (otherwise, Case 1) nor 3 (Fact 5). So one is coloured 2 and the other is coloured 3. Thus, N 1 is saturated and N 122 must be coloured 1, since we are not in Case 1. The vertices N 223 and N 233 cannot receive colour 2 as N 3 is saturated, cannot be both coloured 3, thanks to Fact 5, and cannot be both coloured 1, due to the interference in N 2 . So one of these vertices is coloured 1 and the other is coloured 3; N 2 is saturated and N 112 must be coloured 3. Consequently, N 11 is coloured 2 and N 01 is coloured 3. We then observe that N 01 and N 5 are saturated and that N 001 and N 011 must be both coloured 1. It leads to a contradiction as I N0 (T 2 , w 2 , c) ≥ 3. We conclude that N 44 is coloured 2.-Suppose first that c(N 34 ) = 2. In this case, N 23 and N 33 are both coloured 3 due to the interference in N 3 . Observe that N 12 and N 22 can neither be both coloured 2 (interference in N 3 ) nor 3 (interference in N 23 ). So one is coloured 2 and the other is coloured 3. It implies that N 3 is saturated. Thus, N 223 and N 233 are both coloured 1, due to the interference in N 23 . So N 2 is also saturated. The vertices N 333 and N 334 can neither be both coloured 1 (otherwise, I N233 (T 2 , w 2 , c) ≥ 3) nor 3 (Fact 3). So one of them is coloured 1 and the other is coloured 3. As a consequence, N 23 is saturated, N 22 is coloured 2 and N 12 is coloured 3. But then N 122 and N 222 must be coloured 2 and we have a contradiction as I N22 (T 2 , w 2 , c) ≥ 3. -We obtain that c(N 34 ) = 3. N 23 and N 33 can neither be both coloured 2 (otherwise, Case 1 with N 3 ) nor 3 (Fact 5). So one of them is coloured 2 and the other is coloured 3. It implies that N 4 is saturated and N 55 and N 50 must be coloured 2.

  2 , w 2 , c) ≥ 3. ii. We then conclude that c(N 45 ) = 2. Let us study the possible colourings of N 44 . Suppose now that c(N 44 ) = 3. Observe that N 34 cannot be coloured 3, by Fact 3. If c(N 34 ) = 2, then we are in Case 2b with N 4 . So N 34 is coloured 1 and V 0 is saturated. Observe that N 23 and N 33 can neither be both coloured 2 (otherwise, Case 1 with N 3 ) nor 3 (interference in N 4 ). So one of them is coloured 2, the other is coloured 3 and N 4 is saturated. It implies that N 55 and N 50 must be coloured 2 and, due to the interference in N 45 , that N 445 must be coloured 1. Moreover, N 334 and N 344 can neither be both coloured 1 (interference in N 34 ) nor 2 (interference in N 3

  3. Thus, N 50 is coloured 2, by Fact 3, and N 45 is also saturated. If both N 23 and N 33 are coloured 3, N 4 is saturated and then we have a contradiction to Fact 5, because N 334 , N 344 , N 444 , N 445 and N 455 should be all coloured 1. So among N 23 and N 33 we have one vertex coloured 1, the other is coloured 3 and then N 12 and N 22 must be coloured 3. If N 23 is coloured 1 (and then N 33 is coloured 3), we have that N 2 is saturated and then N 223 and N 233 must be coloured 3. But then we have a contradiction to Fact 5. So N 33 must be coloured 1 (and then N 23 is coloured 3). By Fact 3, we have that N 223 is coloured 1 and then N 2 is also saturated. Consequently, N 233 must be coloured 3 and we have a contradiction asI N23 (T 2 , w 2 , c) ≥ 3. -Suppose now that c(N 34 ) = 1 (so V 0 is saturated). * If c(N 33 ) =2, N 3 is also saturated and then N 12 , N 22 and N 23 must be all coloured 3. However, N 223 and N 233 must be coloured 1, due to interference constraints in N 22 , N 23 and N 3 , which is a contradiction as I N2 (T 2 , w 2 , c) ≥ 3. * So c(N 33 ) = 3. Let us check the possible colourings of N 23 . If N 23 is coloured 2, N 3 is saturated and then N 12 and N 22 are both coloured 3. N 223 and N 233 can neither be both coloured 1 (interference in N 2 ) nor 3 (Fact 5). So one of them is coloured 1, the other is coloured 3 and N 2 is saturated. If N 223 is coloured 3 (and then c(N 233 ) = 1), N 22 is also saturated. In this case, the vertices N 11 , N 112 , N 122 and N 222 must be all coloured 2, contradicting Fact 5. So we conclude that N 223 is coloured 1 and N 233 is coloured 3. Consequently, N 333 and N 334 must be coloured 1 (interference in N 3 and N 33 ) and then N 34 is saturated. Thus, N 344 and N 445 must be coloured 3. It implies that N 4 is saturated and then N 55 and N 50 are both coloured 2. This is a contradiction as I N45 (T 2 , w 2 , c) ≥ 3. We conclude that N 23 is coloured 3. If N 22 is also coloured 3, N 23 is saturated and then N 12 is coloured 2. N 223 and N 233 can neither be both coloured 1 (interference in N 2 ) nor 2 (interference in N 3 ). So one of them is coloured 1, the other is coloured 2 and N 2 and N 3 are both saturated. It implies that N 334 and N 344 are both coloured 1, N 34 is saturated and then N 344 must be coloured 3. But then N 4 is saturated, N 445 must be coloured 2 and we are in Case 1. So N 22 must be coloured 2. If c(N 12 ) = 2, then N 3 is saturated. N 223 and N 233 can neither be both coloured 1 (interference in N 2 ), nor 3 (Fact 3). Thus, one is coloured 1, the other is coloured 3 and N 2 and N 23 are both saturated. Consequently, N 12 , N 122 and N 222 must be all coloured 2, contradicting Fact 3. Therefore, c(N 12 ) = 3, but then N 223 and N 233 cannot be coloured 3 (otherwise, I N23 (T 2 , w 2 , c) ≥ 3). So they are coloured 1 and I N2 (T 2 , w 2 , c) ≥ 3, a contradiction. -We conclude that c(N 34 ) = 3. Let us study the possible colourings of N 55 . * Suppose first that c(N 55 ) = 3. So N 4 and N 5 are saturated. N 23 and N 33 can neither be both coloured 1 (interference in V 0 ) nor 2 (we are not in Case 1). So one of them is coloured 1, the other is coloured 2 and V 0 and N 3 are also saturated. It implies that N 334 and N 344 must be both coloured 1 and that N 50 and N 00 must be coloured 2. Observe then that N 445 and N 455 cannot receive colour 2 (interference in N 45 ) and 3 (N 4 is saturated). So they are both coloured 1 and, by Fact 5, N 444 must be coloured 2. Since N 45 is also saturated, N 555 and N 550 must be coloured 1. But then we have a contradiction because N 500 cannot receive colour 1 (Fact 5), 2 (we are not in Case 1) or 3 (N 5 is saturated). * Now consider that c(N 55 ) = 2. Observe that N 45 is saturated. If N 50 is coloured 3, N 4 and N 5 are also saturated and we have a contradiction to Fact 5, because N 344 , N 444 , N 445 , N 455 , N 555 and N 550 are all coloured 1. So N 50 is coloured 1 and V 0 and N 0 are saturated. N 23 and N 33 can neither be both coloured 2 (we are not in Case 1) nor 3 (Fact 5). So one is coloured 2, the other is coloured 3 and we have that N 3 and N 4 are both saturated. This leads to a contradiction to Fact 5, because N 334 , N 344 , N 444 , N 445 and N 455 are all coloured 1. * We then conclude that N 55 must be coloured 1 (and V 0 is saturated). Again N 23 and N 33 can neither be both coloured 2 nor 3. One of them is coloured 2 and the other is coloured 3 implying that N 3 and N 4 are both saturated. As a consequence, N 334 and N 344 are coloured 1 and N 50 is coloured 2. Thus, N 445 and N 455 are both coloured 1, due to the interference in N 4 and N 45 . So N 444 must be coloured 2 and N 45 is saturated. Consequently, N 555 and N 550 must be both coloured 3 due to the interference in N 45 and N 55. We obtain that N 5 is also saturated and then that N 00 and N 01 are both coloured 2 and both saturated and N 1 is also saturated. So N 23 is coloured 3 and N 33 is coloured 2. Furthermore, N 500 is coloured 1 and N 0 is saturated. But then N 011 , N 11 , N 12 and N 22 are coloured 3, contradicting Fact 5.

  2, only two are consecutive. W.l.o.g., let the three vertices of colour 2 be N 0 , N 1 and N 3 . At least one vertex of N 50 , N 00 , N 01 is coloured 1, otherwise N 0 has four neighbours of the same colour as it and we would be in the previous case. Similarly at least one vertex of N 01 , N 11 , N 12 is coloured 1, otherwise N 1 has four neighbours with its colour and we would be in the previous case. At least one vertex of N 23 , N 33 , N 34 is coloured 1, otherwise N 3 has three consecutive neighbours of the same colour as it and we are in the previous case. Suppose N 01 is coloured 2, then I V0 (T 2 , w 2 , c) ≥ 4.5 and exactly one of N 50 , N 00 and one of N 11 , N 12 is coloured 1 and N 45 , N 55 are coloured 2, otherwise I V0 (T 2 , w 2 , c) ≥ 5. Then I N0 (T 2 , w 2 , c) ≥ 5, a contradiction. So, c(N 01 ) = 1. If both N 50 , N 00 are coloured 2, then I N0 (T 2 , w 2 , c) ≥ 5 with three neighbours coloured 2 and at least four vertices at distance two coloured 2, namely N 3 and three vertices among N 45 , N 55 , N 11 , N 12 (at most one vertex of these could be of colour 1, otherwise I V0 (T 2 , w 2 , c) ≥ 5). So, one of N 50 , N 00 is coloured 1 and all the other vertices in {N 11 , N 12 , N 22 , N 44 , N 45 , N 55 } are coloured 2 implying that I N3 (T 2 , w 2 , c) ≥ 5, a contradiction. (c) No two vertices of colour 2 are consecutive. W.l.o.g, let these vertices be N 0 , N 2 , N 4 . The three neighbours of N 0 (resp. N 1 , N 2 ) in Γ 2 that are not neighbours of V 0 cannot be all coloured 2, otherwise we are in Case (a). So exactly one neighbour of N0 , N 1 , N 2 in Γ 2 is coloured 1, otherwise I V0 (T 2 , w 2 , c) ≥ 5.Furthermore all the other vertices of Γ 2 are coloured 2. Then, if c(N 12 ) = c(N 45 ) = 2, we conclude that I N0 (T 2 , w 2 , c) ≥ 5, a contradiction. Consequently, w.l.o.g., suppose that c(N 12 ) = 1. In this case, N 23 has at least three neighbours coloured 2 and we are in some previous case.3. No vertex has three neighbours coloured with its own colour, but there exists at least one vertex, say V 0 , of colour 1 that has two neighbours coloured 1.(a) These two neighbours are consecutive say N 0 and N 1 . The neighbours of N 3 and N 4 in Γ 2 are all coloured 1, otherwise they would have at least three neighbours with the same colour. Similarly, at least one of N 12 and N 22 is coloured 1, otherwise N 2 would have at least three neighbours also coloured 2.Then, I V0 (T 2 , w 2 , c) ≥ 5, a contradiction.(b) These two neighbours are of the form N i and N i+2 , for some 0 ≤ i ≤ 3. W.l.o.g., let these neighbours be N 0 and N 2 . Thus, the three neighbours of N 4 in Γ 2 , N 34 , N 44 and N 45 are coloured 1 and at least one vertex of N 23 and N 33 (resp. N 55 and N 50 ) is coloured 1. Moreover, at least one vertex of N 01 , N 11 and N 12 must be coloured 1, otherwise N 1 would have three neighbours with its colour. Consequently, I V0 (T 2 , w 2 , c) ≥ 5, a contradiction. These two neighbours are of the form N i and N i+3 , for some 0 ≤ i ≤ 2. W.l.o.g., let these neighbours be N 0 and N 3 . Again, at least three vertices among N 01 , N 11 , N 12 , N 22 and N 23 and at least three other vertices among N 34 , N 44 , N 45 , N 55 and N 50 are coloured 1. Consequently, I V0 (T 2 , w 2 , c) ≥ 5, a contradiction. 4. No vertex has two neighbours of the same colour. Suppose V 0 is coloured 1 and has only one neighbour N 0 coloured 1. Then, its other five neighbours are coloured 2 and N 2 has two neighbours of the colour 2, a contradiction. A weighted 5-improper 2-colouring of (T 2 , w 2 ) is obtained as follows: for

	(c)
	RR n°7590

RR n°7590

http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/ RR n°7590

This is the faster implementation envisioned in[START_REF] Araujo | Weighted improper colouring[END_REF].RR n°7590

http://www.gnu.org/software/glpk/ RR n°7590

http://www.inria.fr ISSN 0249-6399

This work was partially supported by région PACA, ANR Blanc AGAPE (ANR-09-BLAN-0159) and ANR International Taiwan GRATEL (ANR-09-BLAN-0373).