Jean-Claude Bermond
email: jean-claude.bermond@inria.fr

Fatima Zahra Moataz
email: fatzmoataz@gmail.com

On Spectrum Assignment in Elastic Optical Tree-Networks I

Keywords: Elastic optical networks, spectrum assignment, interval coloring, chordal graphs

To face the explosion of the Internet tra c, a new generation of optical networks is being developed; the Elastic Optical Networks (EONs). EONs use the optical spectrum e ciently and flexibly, but that gives rise to more di culty in the resource allocation problems. In this article, we study the problem of Spectrum Assignment (SA) in Elastic Optical Tree-Networks. Given a set of tra c requests with their routing paths (unique in the case of trees) and their spectrum demand, a spectrum assignment consists in allocating to each request an interval of consecutive slots (spectrum units) such that a slot on a given link can be used by at most one request. The objective of the SA problem is to find an assignment minimizing the total number of spectrum slots to be used. We prove that SA is NP-hard in undirected stars of 3 links and in directed stars of 4 links, and show that it can be approximated within a factor of 4 in general stars. Afterwards, we use the equivalence of SA with a graph coloring problem (interval coloring) to find constant-factor approximation algorithms for SA on binary trees with special demand profiles.

Introduction

Elastic Optical Networks (EONs) [START_REF] Gerstel | Elastic optical networking: a new dawn for the optical layer?[END_REF] have been proposed as a potential candidate to replace the traditional Wavelength Division Multiplexing (WDM) networks. In EONs, new technologies such as optical OFDM, adaptive modulation techniques, bandwidth variable transponders, and flexible spectrum selective switches are used to ensure an e cient utilization of the optical resources and to enable a flexible grid as opposed to the WDM fixed-grid. In fact, the optical spectrum in EONs is subdivided into small channels, called slots, which are finer than the 50GHz wavelengths used under WDM. With these slots, small bitrates are not over-provisioned and big bitrates can be satisfied as single entities, under the constraint of contiguity. This constraint dictates that the slots used by a request should be consecutive. This results in an e cient use of the spectrum but it also makes the problems of resource allocation in EONs more di cult than their counterparts in WDM.

The key resource allocation problem in EONs is referred to as Routing and Spectrum Assignment (RSA). In RSA, the input is a set of tra c requests and the objective is to allocate to each request, a path in the optical network and an interval of spectrum slots along that path, minimizing the utilized spectrum. The spectrum allocated to a request has to be contiguous (contiguity constraint), it has to be the same over all links of the routing path (continuity constraint) and requests with paths sharing a link should be assigned disjoint spectrum intervals (non-overlapping constraint). For a recent survey of the literature on RSA, we refer the reader to [START_REF] Talebi | Spectrum management techniques for elastic optical networks: A survey[END_REF]. If the routing is fixed, i.e. a path is predefined for each request, RSA reduces to the problem of Spectrum Assignment (SA).

Related work.

The SA problem is a generalization of the well studied problem of Wavelength Assignment (WA) (WA is the special case of SA in which all requests have equal demands). Since WA has been proved NP-complete in [START_REF] Chlamtac | Lightpath communications: an approach to high bandwidth optical wan's[END_REF], SA is also NP-complete. In fact, SA remains NP-hard even in networks where WA is tractable, particularly in path networks. Indeed, SA has been proved to be equivalent to other problems studied in the literature which we describe in details in Section 2. Using the results obtained for the equivalent problems, SA is NP-complete in paths even if the requests' demands do not exceed 2 slots [START_REF] Buchsbaum | Restricted strip covering and the sensor cover problem[END_REF]. Furthermore, SA is NP-complete in paths with 4 links and unidirectional rings with 3 links [START_REF] Talebi | Spectrum assignment in optical networks: A multiprocessor scheduling perspective[END_REF]. On the positive side, SA can be approximated within a factor of 2 + ✏ in paths, a factor of 4 + ✏ in rings, and a factor of O(log(k)) in binary trees where k is the number of requests [START_REF] Shirazipourazad | On routing and spectrum allocation in spectrum-sliced optical networks[END_REF].

Contribution. In this article, we study the SA problem in trees. We focus on special cases where the tree is a star or a binary tree. By studying these special cases, we hope to gain more insight into the general problem in trees and design a constant-factor approximation algorithm or prove that such algorithm does not exist. We prove that SA is NP-hard in undirected stars of 3 links and in directed stars of 4 links, and show that in general stars it can be approximated within a factor of 4. Afterwards, we use the equivalence of SA with a graph coloring problem (interval coloring) to find constant-factor approximation algorithms for SA on binary trees with special demand profiles. Namely, we examine the cases where the demands are in a set {k, kX} (k, X 2 N ⇤ ), in a set {kX, k(X + 1)} (k, X 2 N ⇤ ), or bounded by D. For the latter case, we give a general approximation when the demands are bounded by D 2 N and then give better approximations for the cases where the demands are bounded by D 2 {3, 4, 5, 6}.

This article is organized as follows. In Section 2, we formally define the SA problem and survey its relation to other problems and its complexity in path networks in particular. Afterwards, we present our results in stars and binary trees in Sections 3 and 4, respectively.

Problem statement and related problems

In this section, we first define the problem of Spectrum Assignment (SA) and then present some related problems and highlight their relation to SA. In the last subsection, we list the results implied by these relations for the complexity of SA in paths.

Spectrum Assignment

An instance (N , R) of the problem consists of a graph N = (N, L) and a set of requests R. The graph N models an optical network with N as the set of nodes and L as the set of links. A request r 2 R consists of a path P (r) in N and a spectrum demand d(r) 2 N (number of spectrum slots). We say that two requests r, r 0 2 R are conflicting if their paths P (r) and P (r 0 ) share a link. A spectrum assignment of (N , R) is a mapping f from R to N ⇤ such that for every pair of conflicting requests r, r 0 2 R, we have {f (r), . . . , f(r) + d(r) 1} \ {f (r 0 ), . . . , f(r 0 ) + d(r 0 ) 1} = ;. We say that all the slots in {f (r), . . . , f(r) + d(r) 1} are occupied by r. In this article, we consider slots as integers (which will be useful for the relation with colors in interval colorings); however other authors consider slots as intervals of unit length. In fact the set of slots {f (r), . . . , f(r) + d(r) 1} corresponds to the spectrum interval ]f (r) 1, f(r)+d(r) 1]. The span of a spectrum assignment f , denoted s(f ), is the smallest integer s such that for each request r 2 R, f (r) + d(r) 1  s. The span of an instance (N , R), denoted by s(N , R) is the minimum of the spans over all possible spectrum assignments. We formulate the Spectrum Assignment problem as follows:

Problem 1 (Spectrum Assignment (SA)). Given an instance (N , R), compute s(N , R).

For an instance (N , R) of SA, the load of a link `, denoted by ⇡(`), is the sum of the demands of the requests using `and the load of an instance, denoted by ⇧(N , R), is the maximum load over all its links. It is straightforward that ⇧(N , R)  s(N , R). In the approximations we obtain for SA in this article, the span is usually upper bounded by a function of the maximum load.

The greedy algorithm for SA is an algorithm which assigns spectrum to requests ordered in a given order r 1 , . . . , r n such that a request r i is assigned the smallest positive integer g(r i ) such that {g(r i ), . . . , g(r i ) + d(i) 1} \ {g(r j ), . . . , g(r j ) + d j 1} = ; for each r j in {r 1 , . . . , r i 1 } conflicting with r i . It is important to note here that every optimal result can be obtained by this algorithm (once it is provided with the correct order of the vertices). We will use this algorithm many times in the rest of this article.

Figures 1a,1b illustrate an instance of SA on a binary tree with 5 requests. Note that the order of the requests with which the greedy algorithm is applied has a direct impact on the number of spectrum slots used. In the example of Figure 1a, applying the greedy algorithm in the order r 1 , r 2 , r 3 , r 4 , and then r 5 results in the use of 7 spectrum slots respectively {1}, {2, 3}, {4}, {5, 6, 7}, and {5, 6} , while applying the algorithm in the order r 3 , r 1 , r 5 , r 2 , and then r 4 results in the use of only 5 spectrum slots: slots {1}, {2}, {2, 3}, {4, 5}, and {3, 4, 5} for r 3 , r 1 , r 5 , r 2 , and r 4 , respectively. The span of this instance is exactly 5, as the load is equal to 5 on the two links used by r 3 .

Related problems

Interval Coloring

As pointed out in [START_REF] Shirazipourazad | On routing and spectrum allocation in spectrum-sliced optical networks[END_REF], the problem of SA is also equivalent to a graph coloring problem called Interval Coloring (IC). An interval coloring or a contiguous coloring [START_REF] Golumbic | Algorithmic Graph Theory and Perfect Graphs[END_REF] of a vertex-weighted graph (G = (V, E), w) is a mapping f :

V ! N ⇤ such that for every v, v 0 2 V , if (v, v 0 ) 2 E then {f (v), . . . , f(v) + w(v) 1} \ {f (v 0 ), . . . , f(v 0 ) + w(v 0 ) 1} = ;
. The number of colors used by an interval coloring f , denoted by f (G, w) is the smallest integer s such that for each vertex

v 2 V , f (v) + w(v) 1  s.
The interval chromatic number of a weighted graph (G, w), denoted by (G, w), is the smallest number of colors needed to color the vertices with intervals, i.e. it is the minimum of f (G, w) among all possible interval colorings f of (G, w). The interval coloring problem is defined as follows.

Problem 2 (Interval Coloring (IC)). Given a vertex-weighted graph (G, w), compute (G, w).

To see the equivalence between SA and IC we do the following. For an instance (N , R) of SA, we create a weighted graph (G = (V, E), w) modeling the dependency between the di↵erent requests called the conflict graph. We associate to every request r 2 R a vertex v r in V . We add an edge between two vertices v r and v r 0 if the corresponding requests r and r 0 are conflicting. The weight w(v r ) of each vertex v r is equal to the demand of the corresponding request r (i.e. w(v r ) = d(r)). Figure 1c shows the conflict graph associated to the SA instance of Figure 1a.

If (N , R) is an instance of SA and (G, w) is its conflict graph, then finding a spectrum assignment of (N , R) is equivalent to finding an interval coloring of (G, w) and s(N , R) = (G, w).

Complexity of IC.

The problem of IC has been introduced in [START_REF] Golumbic | Algorithmic Graph Theory and Perfect Graphs[END_REF] where its relation to other problems such as DSA has been highlighted. It has also been proved in [START_REF] Golumbic | Algorithmic Graph Theory and Perfect Graphs[END_REF] that IC is equivalent to the problem of finding, for a vertex-weighted graph, an acyclic orientation which minimizes the weight of the longest path, where the length of a path is the sum of the weights of its vertices. The complexity of DSA implies that IC is strongly NP-complete in interval graphs. IC is also strongly NP-complete in proper interval graphs [START_REF] Shalom | On the interval chromatic number of proper interval graphs[END_REF]. On the positive side, IC is polynomial in comparability graphs [START_REF] Golumbic | Algorithmic Graph Theory and Perfect Graphs[END_REF] and can be approximated within a factor of 2 + ✏ in interval graphs [START_REF] Buchsbaum | Opt versus load in dynamic storage allocation[END_REF], a factor of 2 for proper interval graphs [START_REF] Shalom | On the interval chromatic number of proper interval graphs[END_REF] and claw-free chordal graphs [START_REF] Confessore | An approximation result for the interval coloring problem on claw-free chordal graphs[END_REF], and a factor of O(log(n)) in chordal graphs where n is the number of vertices [START_REF] Pemmaraju | Approximating interval coloring and max-coloring in chordal graphs[END_REF].

Since the conflict graph associated to an instance of SA in a path is an interval graph (and vice versa), all the results established for IC in interval graphs apply to SA in paths. In section 4, we will use the fact that the conflict graph associated with a binary tree is a chordal graph to obtain results for SA in binary trees using interval coloring of chordal graphs.

Scheduling Tasks on Multiprocessor Systems

It has been proved in [START_REF] Talebi | Spectrum assignment in optical networks: A multiprocessor scheduling perspective[END_REF] that SA in a network of k links can be reduced to the problem of Scheduling Tasks on Multiprocessor Systems (STMS) with k processors. In the STMS problem, we are given a set of n tasks and a set of identical processors, a processing time d(j) and a prespecified set P j of processors for each task j, j 2 {1, . . . , n}. The objective is to schedule the tasks so as to minimize the makespan C max = max j C j , where C j denotes the completion time of task j, under the following constraints: (1) preemptions (interruptions of a task) are not allowed, (2) each task must be processed simultaneously by all processors in P j , and (3) each processor can work on at most one task at a time.

Given an instance (N , R) of SA, an instance of STMS is constructed as follows. For each link `of N , we associate a processor w `, and for each request r in R with path P (r) and demand d(r), we associate a task t r with processing time d(r) and a set of processors {w `| `2 P (r)}. The makespan is then the span of the instance of SA.

Complexity of STMS. Note that the relation above is only in one direction as there exist instances of STMS for which there is no corresponding instance of the SA problem. However for 3 processors we can associate to an instance of STMS an instance of SA in an unidirectional ring with 3 links (each processor being associated to one of the links). It has been shown in [START_REF] Hoogeveen | Complexity of scheduling multiprocessor tasks with prespecified processor allocations[END_REF] that the problem of STMS is strongly NP-complete even if the number of used processors is at most 3. Using this result, it is proved in [START_REF] Talebi | Spectrum assignment in optical networks: A multiprocessor scheduling perspective[END_REF] that the SA problem is strongly NP-complete in an unidirectional ring with 3 links. On the positive side, it has been proved in [START_REF] Goemans | An approximation algorithm for scheduling on three dedicated machines[END_REF] and [START_REF] Huang | A simple linear-time approximation algorithm for multi-processor job scheduling on four processors[END_REF] that STMS can be approximated within 7 6 and 1.5 when the number of processors is 3 and 4, respectively. Theorem 1 follows from these approximations.

Theorem 1. There are approximation algorithms with ratios 7 6 and 1.5 for the Spectrum Assignment problem in networks with 3 and 4 links, respectively.

Dynamic Storage Allocation

When the network is a path, the SA problem is equivalent to the problem of Dynamic Storage Allocation (DSA). In the DSA problem, we are given a set A of items to be stored, each a 2 A having size d(a), an arrival time ↵(a), and a departure time (a) (with (a) > ↵(a)). A storage allocation for A is a function f : A ! N ⇤ which associates to each item a 2 A a storage interval I(a) = {f (a), . . . , f(a)+d(a) 1} such that for all a, a 0 2 A with a 6 = a 0 , if ]↵(a), (a)]\]↵(a 0 ), (a 0 )] is not empty, then I(a) \ I(a 0 ) is empty. The storage size used by a storage allocation f denoted by s(f ) is the smallest integer s such that for each item a 2 A, f (a) + d(a) 1  s. The objective in DSA is to find a storage allocation which minimizes the used storage size.

If we consider the time interval as a path network and each of the items to be stored as a request, we can see the equivalence between the problem of SA in paths and the DSA problem. In more details, given an instance of SA on a path (v 1 , . . . , v k ), we associate to each request r with demand d(r), an item a r of size d(r). We also associate to each vertex v i of the path network time i. Let v i and v j be the endvertices of the path P (r) of the request r (i < j), then we choose for the associated item a r the arrival time ↵(a r ) = i and the departure time (a r ) = j. The fact that two requests r and r 0 are conflicting corresponds to the fact that the time intervals ]↵(a r ), (a r )] and ]↵(a r 0 ), (a r 0 )] intersect. Then a spectrum assignment with span corresponds to a storage allocation using a storage size . Conversely using the opposite transformation we can associate to an instance of DSA an instance of SA on a path.

Complexity of DSA. The problem of DSA has been extensively studied. It has been proved that DSA is strongly NP-complete, even when restricted to instances where the storage size of all items is in {1, 2}. The proof of NP-completeness is by reduction from the 3-PARTITION problem and can be found in the appendix of [START_REF] Buchsbaum | Restricted strip covering and the sensor cover problem[END_REF]. On the positive side, many approximation algorithms have been proposed to solve DSA. The first proposed algorithms are based on a greedy algorithm called First Fit (FF) and its performance for online coloring of interval graphs. The relation between online coloring of interval graphs and dynamic storage allocation can be found in [START_REF] Chrobak | On some packing problem related to dynamic storage allocation[END_REF]. Using FF a constant approximation was proved in [START_REF] Kierstead | The linearity of first-fit coloring of interval graphs[END_REF] and a ratio of 6 was given in [START_REF] Kierstead | A polynomial time approximation algorithm for dynamic storage allocation[END_REF]. Gergov has adopted another approach not using FF, yielding an approximation of 5 and 3 sequentially in [START_REF] Gergov | Approximation algorithms for dynamic storage allocation[END_REF] and [START_REF] Gergov | Algorithms for compile-time memory optimization[END_REF]. In his approach, Gergov defines and uses a 2-allocation which is a storage allocation where two items but not three are allowed to overlap. A better approximation has been achieved in [START_REF] Buchsbaum | Opt versus load in dynamic storage allocation[END_REF] where the authors use the idea of boxing items to design a 2 + ✏-approximation algorithm. Better approximations were achieved for DSA with restricted item sizes. In [START_REF] Li | New approximation algorithms for some dynamic storage allocation problems[END_REF], the authors present a 4 3 -approximation algorithm when the maximum size is 2, and a 1.7-approximation algorithm when the maximum size is 3. In [START_REF] Murthy | Approximation algorithms and heuristics for the dynamic storage allocation problem[END_REF], it is proved that for instances with sizes of 1 and X, an approximation of ratio 2 1 X can be guaranteed. All these results established for DSA apply, by equivalence, to SA in paths.

Spectrum Assignment in paths

The results deduced from the equivalence to the problems defined above can be summarized as follows for path networks.

• With respect to the number of links, SA is NP-complete in path networks with 4 links and polynomial in paths with at most 3 links [START_REF] Talebi | Spectrum assignment in optical networks: A multiprocessor scheduling perspective[END_REF], and it can be approximated within a factor of 1.5 in paths with 4 or 5 links [START_REF] Talebi | Spectrum assignment in optical networks: A multiprocessor scheduling perspective[END_REF].

• With respect to the demands, SA is strongly NP-complete even if the requests have demands in the set {1, 2} [START_REF] Buchsbaum | Restricted strip covering and the sensor cover problem[END_REF]. It can be approximated within a factor of 4 3 and a factor of 1, 7 when the maximum demand is 2 and 3, respectively [START_REF] Li | New approximation algorithms for some dynamic storage allocation problems[END_REF]. It also can be approximated within a factor of 2 1

X when the demands are in the set {1, X} [START_REF] Murthy | Approximation algorithms and heuristics for the dynamic storage allocation problem[END_REF].

• In general, SA in paths can be approximated in paths within a factor of 2 + ✏ [START_REF] Buchsbaum | Opt versus load in dynamic storage allocation[END_REF] and it can be approximated within a factor of 2 when the paths of the requests are such that no path is strictly included in another [START_REF] Shalom | On the interval chromatic number of proper interval graphs[END_REF].

Spectrum Assignment in stars: hardness and approximability results

A star is a tree-network with at most one node of degree at least 2. The problem of wavelength assignment (WA) is NP-complete in undirected stars, but polynomial in directed stars [START_REF] Beauquier | Communication dans les réseaux optiques par multiplexage en longueur d'onde[END_REF].

We prove in this section that SA is not only NP-complete in undirected stars but also in directed stars with 4 links. On the positive side, we prove the existence of a 4-approximation algorithm for the general case.

Theorem 2. The problem of Spectrum Assignment is strongly NP-complete in undirected stars with 3 links.

Proof. It was shown in [START_REF] Talebi | Spectrum assignment in optical networks: A multiprocessor scheduling perspective[END_REF] that the SA problem is strongly NP-complete in a 3-link unidirectional ring (see subsection 2.2.2). Let us consider an instance of SA in a 3-link ring C = (l 1 , l 2 , l 3 ) with a request set R. Let us build a star S with three links l 0 1 , l 0 2 and l 0 3 , and a set of requests R 0 defined as follows. For each request r 2 R using at most 2 links, we create a request r 0 in R 0 such that if the path of r in C is P (r) = l i , i 2 {1, 2, 3}, then the path of r 0 in S is P (r 0 ) = l 0 i , and if

P (r) = l i l j , then P (r 0 ) = l 0 i l 0 j . Solving SA in (C, R) is equivalent to solving SA in (S, R 0 ).
Theorem 3. The problem of Spectrum Assignment is weakly NP-complete in directed stars with 3 ingoing links and one outgoing link or 3 outgoing links and one ingoing link. Proof. The proof is by reduction from the 2-PARTITION problem. In the 2-PARTITION problem, we are given a set A of k integers a 1 , a 2 , . . . , a k such that B = P k j=1 a j and the objective is to decide whether A can be partitioned into two disjoint sets A 1 and A 2 such that P aj 2A1 a j = P aj 2A2 a j . Given an instance of the 2-PARTITION problem with a set of k integers A = {a 1 , a 2 , . . . , a k } such that B = P k j=1 a j , we create an instance of the Spectrum Assignment problem in a 4-link directed star network S (Figure 2a) and a set of requests R. The star S has 3 ingoing links l 1 ,l 2 , and l 3 and one outgoing link l 4 . The set of requests R consists of the requests presented in Figure 2b: requests r a , r b , r c , r 1 , and r 2 and for every integer a i in the set A, a request r i 3 with demand a i and using link l 3 . We prove that finding a spectrum assignment for (S, R) with span 3 2 B is equivalent to finding a partition of A into two sets A 1 and A 2 such that

l 1 l 3 l 2 l 4 (a) Star S request demand path r a B/2 l 1 l 4 r b B/2 l 2 l 4 r c B/2 l 3 l 4 r 1 B l 1 r 2 B l 2 r i 3 , 1  i  k a i l 3 (b) Requests R l 1 l 2 l 3 l 4 B 3B/2 B/2 1 r 1 r a r 2 r b r c A 2 A 1 r a r b (c) Spectrum assignment
P aj 2A1 a j = P aj 2A2 a j = B 2 . In fact, if there is a partition of A into A 1 and A 2 such that P aj 2A1 a j = P aj 2A2 a j = B
2 , then we can assign spectrum as shown in Figure 2c. Now let us suppose there is a spectrum assignment for (S, R) with span 3 2 B. There are two possible symmetric assignments to the requests on links l 1 and l 2 . We suppose we assign to r 1 , r a , r 2 and r b spectrum intervals {1, . . . , B}, {B + 1, . . . , 3 2 B}, { B 2 + 1, . . . , 3 2 B}, and {1, . . . , B 2 },, respectively (the analysis is similar for the other assignment). This assignment forces request r c to use the interval { B 2 , +1 . . . , B}, and the other requests on link l 3 will have to be partitioned into two sets of the same size B 2 .

Theorem 4. The problem of Spectrum Assignment in directed stars with at most 3 links or exactly 2 ingoing links and 2 outgoing links can be solved in polynomial time.

Proof. In all of these cases, the span is equal to the maximum load and the greedy algorithm with specific orders can achieve the optimal span.

• When the star has only ingoing or outgoing links, the problem is trivial since any conflicting requests use the same link and the greedy algorithm with any order can achieve the optimal span.

• For the case where the star is a directed path of length 2, an optimal spectrum assignment consists in using the greedy algorithm with an order where the requests using two links come first. This way, the spectrum span will be defined by the link with the maximum load.

• For the case where the star has two ingoing links l 1 and l 2 and one outgoing link l 3 (or the opposite), an optimal spectrum assignment consists in using the greedy algorithm with an order where the requests using l 1 and l 3 come first and the requests using l 2 and l 3 come last. Indeed let A i3 be the sum of the demands of the requests using l i and l 3 for i 2 {1, 2} and let A i be the sum of the demands of the requests using only link l i for i 2 {1, 2, 3}.

Then the span of the spectrum used on link l 1 is A 13 + A 1 = ⇡(l 1 ), and that on links l 2 and

l 3 is equal to max(A 13 + A 3 , A 2 ) + A 23 = max(⇡(l 2 ), ⇡(l 3
)), and so the span of this spectrum assignment is equal to the maximum load of the instance.

• When the star has 2 ingoing links l 1 and l 2 and 2 outgoing links l 3 and l 4 , let A ij be the sum of the demands of the requests using l i and l j for i 2 {1, 2} and j 2 {3, 4} and let A i be the sum of the demands of the requests using only link l i for i 2 {1, 2, 3, 4}. First, the requests using l 1 and l 3 and the requests using l 2 and l 4 are assigned with the greedy algorithm; the span of the spectrum used on links l 1 and l 3 is equal to A 13 , and the span of the spectrum used on links l 2 and l 4 is equal to A 24 . Afterwards, the requests using only one link are assigned; the span of the spectrum used on links l 1 , l 2 , l 3 , and l 4 is A 13 + A 1 , A 24 + A 2 , A 13 + A 3 , and A 24 + A 4 , respectively. Finally, the requests using l 1 and l 4 and the requests using l 2 and l 3 are assigned with the greedy algorithm; the span of the spectrum used on links l 1 and l 4 is equal to max(A 13 + A 1 , A 24 + A 4 ) + A 14 = max(⇡(l 1 ), ⇡(l 4 )), and the span of the spectrum used on links l 2 and l 3 is equal to max(A

13 + A 3 , A 24 + A 2 ) + A 23 = max(⇡(l 2 ), ⇡(l 3 )).
This means that the span of this spectrum assignment is equal to the maximum load of the instance.

Now we give a 4 approximation algorithm for any star. The theorem follows from a more general result valid for any network, when the lengths of the paths associated to the requests have a bonded size.

Theorem 5. Let (N , R) be an instance of SA. If the length of the paths associated to the requests in R is at most ↵, then the greedy algorithm gives a 2↵-approximation for the Spectrum Assignment problem. In particular there is a 4-approximation polynomial-time algorithm for the Spectrum Assignment problem in stars.

Proof. Let (N , R) be an instance of SA. Let the requests of R be ordered in the non-increasing order of demands r 1 , r 2 , . . . , r q (i.e., d(r 1 ) d(r 2 ) • • • d(r q )). Let ⇧ be the maximum load. We will use at most 2↵⇧ slots to allocate spectrum to the requests of R. Suppose that we have already assigned spectrum to the first requests r j , j < i with the span 2↵⇧ and consider the request r i with demand d(r i ) = d. For each link l of the path P (r i ), let R i (l) be the set of requests already assigned conflicting with r i on the link l. As the load of the link l is at most ⇧, the sum of the demands of the requests of R i (l) is at most ⇧ d. Since each of these requests has demand at least d, we have at most ⇧ d d requests in R i (l). This implies that the path P (r i ) has at most ↵(⇧ d) d requests conflicting with r i which have been already assigned spectrum. Consider the slots not occupied by these requests (available slots). If there exists an interval of d or more available slots below these requests or between two requests, we can assign to request r i the first such interval.

Otherwise, between slot 1 and the first slot occupied by the conflicting requests and between the last slot occupied by a request and the first slot of the next request there are at most d 1 available slots. As there are at most ↵(⇧ d) d requests conflicting with r i , we have at most ↵(⇧ d) d such intervals. As the requests in R i (l) occupy at most (⇧ d) slots, we have at most ↵(⇧ d) slots occupied by the conflicting requests and at most ↵(⇧ d) d (d 1) slots available where we cannot provision r i . Altogether, we have a number of non usable slots equal to

↵(⇧ d)+ ↵(⇧ d) d (d 1) = 2↵⇧ 2↵d ↵(⇧ d) d
. So, there is an interval of 2↵d + ↵(⇧ d) d available contiguous slots above all the requests conflicting with r i . Then, we can allocate to r i d contiguous slots in this interval. In particular, in the case of stars where ↵ = 2, we obtain a 4-approximation. This approximation algorithm for stars together with the 2 + ✏-approximation algorithm for paths presented in [START_REF] Buchsbaum | Opt versus load in dynamic storage allocation[END_REF], imply a constant factor approximation for tree networks which are spiders. A spider is a tree with one vertex of degree at least 3 and all others with degree at most 2. Theorem 6. There is a (6 + ✏)-approximation for the Spectrum Assignment problem in spiders.

Proof. Let (S, R) be an instance of SA in a spider. Let v be the vertex of S of degree at least 3 and let S 0 be the star induced by v and all the vertices of S which are at distance 1 from v. We first consider the set of requests R 1 using an edge of S 0 . For a request r of R 1 we associate the restricted request r 0 in S 0 with path the subpath of r restricted to S 0 and same demand as r. We use the 4-approximation presented in Theorem 5, to allocate spectrum to these restricted requests using the star S 0 . That induces a spectrum assignment to the requests of R 1 , as two such requests intersect if and only if their restricted requests intersect. Now we consider the other set of requests R 2 which are included in some path P of the paths of S \ S 0 . We use the 2 + ✏approximation algorithm to allocate spectrum to the requests of R 2 using P . We can use the same spectrum range for two di↵erent paths as they have no link in common. So altogether we get a (6 + ✏)-approximation algorithm.

Spectrum Assignment in binary trees with restricted weight requests

The SA problem in binary trees (trees in which each node has degree at most three) has been studied in [START_REF] Shirazipourazad | On routing and spectrum allocation in spectrum-sliced optical networks[END_REF]. It has been proved that SA can be approximated within a ratio of O(log(k))

where k is the number of requests. The proof is based on the equivalence between SA and the problem of Interval Coloring (IC). In fact, the conflict graph of an instance of SA in a binary tree corresponds to an edge intersection graph of paths in a binary tree. These graphs have been proved to be chordal graphs in [START_REF] Golumbic | The edge intersection graphs of paths in a tree[END_REF][START_REF] Golumbic | Representing edge intersection graphs of paths on degree 4 trees[END_REF]. Note that the edge intersection graph of paths in a general tree are not chordal, contrarily to a strange remark in [START_REF] Golumbic | The edge intersection graphs of paths in a tree[END_REF] p.151, where it is claimed that edge intersection and vertex intersection give rise to identical classes of graphs in the case of subtrees of trees (although they give just after an example of an edge intersection graph of paths in a tree which is not chordal). In fact it has been shown in [START_REF] Gavril | The intersection graphs of subtrees in trees are exactly the chordal graphs[END_REF] that a graph is chordal if and only if it is the vertex intersection graph of subtrees of a tree. In contrary any graph can be represented as the edge intersection graph of subtrees in a star. It is easy to build examples of non chordal graphs which are edge intersection graph of paths in a tree. For example consider a star with central vertex 0 and end vertices 1 to n. Consider the paths of length 2: i, 0, i + 1 for i = 1, . . . , n (indices modulo n). The edge intersection graph of these paths is the cycle of length n. More details on the edge intersection graphs of paths in a tree can be found in [START_REF] Golumbic | Representing edge intersection graphs of paths on degree 4 trees[END_REF][START_REF] Monma | Intersection graphs of paths in a tree[END_REF].

Therefore in this section we give some constant-factor approximation algorithms for the problem of interval coloring in chordal graphs with special demand profiles. Using the fact that the conflict graph of an instance of SA in a binary tree is chordal, we deduce constant-factor approximation algorithms for the problem of spectrum assignment in binary trees with the same special demand profiles. Namely, we examine the cases where the demands are in a set {k, kX} (k, X 2 N ⇤ ), in a set {kX, k(X + 1)} (k, X 2 N ⇤ ), or bounded by D. For the latter case, we give a general approximation when the demands are bounded by D 2 N and then give better approximations for the cases where the demands are bounded by D 2 {3, 4, 5, 6}. It is important to recall here that even if the network is a path and the demands are bounded by 2, SA is strongly NP-complete. We first start by giving some definitions and then we state our results.

Definitions

A chord of a cycle C in a graph is an edge of the graph connecting two vertices that are not adjacent in C. A graph G is chordal if every cycle of G with at least 4 vertices has a chord. One important property of chordal graphs is their perfect elimination order. The perfect elimination order (PEO) of a graph is an ordering x 1 , x 2 , . . . , x n of the vertices of the graph such that for i = 1, . . . , n 1, the neighbors of x i in G[{x i+1 , . . . , x n }] 1 form a clique. It is well known that a graph is chordal if and only if it has a perfect elimination order. Paper [START_REF] Tarjan | Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs[END_REF] describes a linear time algorithm called maximum cardinality search that can be used to determine if a given graph has a perfect elimination order and construct such an ordering if it exists. Throughout the remainder of this article, we use the reverse perfect elimination order (RPEO) in the design of some algorithms. Note that if v 1 , v 2 , . . . , v n is a RPEO of the vertices of a chordal graph, then for i = 2, . . . , n, the neighbors of v i in G[{v 1 , . . . , v i 1 }] form a clique. Another tool we will be using is the greedy algorithm for IC. Defined similarly to the greedy algorithm for SA, the greedy algorithm for IC, (also called in the literature the First Fit algorithm (FF)) is an algorithm which assigns colors to vertices in a given order v 1 , . . . , v n such that a vertex v i is assigned the smallest positive integer g(v i ) such that {g(v i ), g(v i )+w(v i ) 1}\{g(v j ), g(v j )+w(v j ) 1} = ; for each v j in {v 1 , . . . , v i 1 } which is adjacent to v i . In a weighted graph (G = (V, E), w), we define the weight of a subset S ✓ V to be the quantity w(S) = P v2S w(v). The maximum weighted clique is a clique with the biggest weight. The density of (G = (V, E), w) is the weight of the maximum weighted clique and is denoted by (G, w). It is straightforward that (G, w)  (G, w), where (G, w) is the interval chromatic number of (G, w).

In the remainder of this section, we present our results for SA in binary trees with bounded demands as corollaries after proving theorems for IC in weighted chordal graphs with bounded weights using the fact that every conflict graph of an instance of SA in a binary tree is a chordal graph [START_REF] Golumbic | The edge intersection graphs of paths in a tree[END_REF].

Demands k and kX

In this section, we present an approximation algorithm for the SA problem when the demand of each request is either k or kX, with k, X 2 N ⇤ . We start by proving the following theorem for interval coloring in chordal graphs.

Theorem 7. Let (G, w) be a weighted chordal graph with weights in the set {k, kX}. There exists a polynomial time algorithm that finds an interval coloring of (G, w) with 2 (G, w) kb (G,w) kX c colors.

Proof. It has been proved in [START_REF] Murthy | Approximation algorithms and heuristics for the dynamic storage allocation problem[END_REF] that there is an algorithm to find a (2 1 X )-approximation for the problem of interval coloring in interval graphs whenever there are only two weights 1 and X. We generalize this algorithm for chordal graphs as follows.

Without loss of generality, we only do the proof for k = 1. Indeed to color a graph (G, w) with weights in {k, kX}, we can transform it to a graph (G, w 0 ) with weights in {1, X}, color (G, w 0 ) and then transform the colors we found into intervals of colors of size k. So, let (G, w) be a weighted chordal graph with weights in {1, X} and let = (G, w) be its density. We will use 2 b X c colors to color (G, w) as follows. We partition the colors into two sets. The first set S 1 contains colors from 1 to and the second set S 2 contains colors from + 1 to 2 b X c. We order the vertices of G in the reverse perfect elimination order. Let v 1 , . . . , v n be the obtained ordering. Recall that the neighbors of v i in {v 1 , . . . , v i 1 } form a clique in the graph induced by {v 1 , . . . , v i 1 }. We use the greedy algorithm to assign colors to the vertices in this order with the additional property that colors assigned to a vertex are either included in S 1 or S 2 (we cannot use colors from both sets). We prove that with this algorithm, all vertices will be assigned colors in S 1 or S 2 .

• All vertices of weight 1 will have a color in S 1 . In fact, if a vertex v i of weight 1 cannot be assigned a color in S 1 , then its neighbors in {v 1 , . . . , v i 1 } occupy all colors of S 1 . This implies that v i and its neighbors in {v 1 , . . . , v i 1 }form a clique of size + 1 a contradiction.

• For vertices of weight X, suppose that there is a vertex v j of weight X to which we cannot assign colors neither in S 1 nor in S 2 . The minimum number of colors used in S 1 that can make it not possible to color v j with colors from S 1 is b X c (X 1 free colors then 1 occupied color, then X 1 free colors and 1 occupied color . . . ). Therefore the weight of the neighbors of v j in {v 1 , . . . , v j 1 } which use colors in S 1 is at least b X c. Since we cannot assign colors from S 2 to v j and knowing that only vertices of the same weight X use colors from S 2 with the greedy algorithm, we deduce that the sum of the weights of the neighbors of v j in {v 1 , . . . , v j 1 } which use colors in S 2 is at least |S 2 | (X 1). So v j and its neighbors form a clique of size at least

X + b X c + |S 2 | (X 1) + 1 as |S 2 | = b X c
. This implies that the density of G is at least + 1, a contradiction.

Thanks to Theorem 7, we can deduce the following corollary.

Corollary 1. Let I be an instance of SA in a binary tree such that the demands of requests are in the set {k, kX} and the span of I is OPT . There is a polynomial-time algorithm that finds a spectrum assignment for I with span less than (2 1 X )OPT + k. In the rest of this subsection, we find a lower bound on the interval chromatic number of chordal graph with weights in {k, kX}. Theorem 8. There exists a family of weighted chordal graphs (G m ) m2N ⇤ , with weights in the set {k, kX}, for which the ratio between the interval chromatic number and the density tends to 2 1 X when m tends to infinity.

Proof. For m > 0, we build the weighted graph G m of density k(mX 2 + 1) as follows.

• mX 2 + 1 vertices of weight k each forming a "big" clique.

• For each subset S of mX + 1 vertices of the big clique, we add m(X 1) new vertices of weight kX each. These vertices form a clique with the vertices of S.

In any interval coloring of G m , there exists an integer in {0, . . . , kX 1} such that the "big" clique uses mX + 1 colors congruent to modulo kX. Suppose that this is not true and that the big clique uses for each integer i in {0, . . . , kX 1} at most mX colors which are congruent to i modulo kX. This means that the number of colors used is at most kmX 2 . This is not possible since this maximum clique has weight k(mX 2 + 1). Let S be a subset of mX + 1 vertices of the big clique using colors that are congruent to modulo kX. Vertices of S form a clique with m(X 1) vertices of weight kX. Each of these vertices uses a color congruent to modulo kX. In total, m(2X 1) + 1 colors which are congruent to are used. All the colors congruent to another value appear at least m(2X 1) times. This implies that the total number of colors used is at least kmX(2X 1) + 1. The ratio between the chromatic number and the density is then at least

kmX(2X 1)+1 k(mX 2 +1) = 2 1 X (2k 1)X k kX(mX 2 +1
) . When m goes to infinity, this ratio goes to 2 1 X . Finally, let us prove that G m is chordal. Let C be a cycle in G m . If C is entirely included in the big clique or in a clique of the second type, then the subgraph induced by the vertices of C is complete and C has a chord. Otherwise, if C is not entirely included in a clique, then C contains two vertices of the big clique which are not adjacent in the cycle and the edge between them is a chord.

Demands kX and k(X + 1)

In this section, we present an approximation algorithm for the SA problem when the demand of each request is either kX or k(X + 1). We start by proving the following theorem for interval coloring in chordal graphs. Theorem 9. Let (G, w) be a weighted chordal graph with weights in {kX, k(X + 1)}. There is a polynomial time algorithm to color G with at most X+1 X (G, w) colors.

Proof. Let (G, w) be a weighted chordal graph with weights in {kX, k(X +1)}. Let m = b (G,w) kX c; we prove that we can color (G, w) with k(X + 1)m colors. We partition the set of colors {1, . . . , k(X + 1)m} into m contiguous intervals I i , 1  i  m of size k(X + 1) each. Let us order the vertices of (G, w) in the RPEO order. We use the greedy algorithm to color the vertices in this order using for each vertex colors from exactly one interval I i , 1  i  m. Suppose that we cannot color some vertex v j , this means that each interval I i , 1  i  m, contains a neighbor of v j with weight at least kX (recall that the weights are either kX or k(X + 1)). Since the neighbors of v j which appear first in the RPEO form a clique with v j , we have a clique of weight at least mkX + kX > (G, w) which is not possible. Therefore we can color all the vertices. Theorem 9 implies the following corollary.

Corollary 2. There is a X+1 X -approximation algorithm for the Spectrum Assignment problem in binary trees when the demands of the requests are in the set {kX, k(X + 1)}.

Maximum demand D

In this section, we present an approximation algorithm for the SA problem when the maximum demand is D.

Theorem 10. Let (G, w) be a weighted chordal graph with maximum weight W . There is a polynomial time algorithm that finds an interval coloring of (G, w) with at most 2 log 2 (W ) (G, w) colors.

Proof. The proof is inspired from that of [START_REF] Pemmaraju | Approximating interval coloring and max-coloring in chordal graphs[END_REF] which presents a O(log 2 (n))-approximation where n is the number of vertices.

Let (G, w) be a weighted chordal graph with maximum weight W . Let us partition the set of vertices V into k subsets S i , i 2 {1, . . . , k} such that for each vertex v 2 S i , w(v) 2 [a i , b i ], with a i and b i integers, a 1 = 1, a i+1 = b i + 1 and b k = W . We first ignore the weights and optimally color each graph G i induced by the subset S i . As the graphs are chordal, we can color the vertices of G i with !(G i ) colors where !(G i ) is the clique number of G i . Afterwards, we replace the color of each vertex v 2 G i by an interval of w(v) colors. This way, we obtain an interval coloring of G i with at most b i !(G i ) colors. Therefore, the vertices of G can be colored with c colors where

c = k P i=1 b i !(G i ). Note that a i !(G i )  (G, !), which implies that c  k P i=1 bi ai (G, w) Let us choose b i = 2a i for i < k. We will have then a i = 2 i 1 for i  k and b i = 2 i+1 2 for i < k. If 2 h  W  2 h+1 2, then we choose k = h = blog 2 (W )c and we will have c  2blog 2 (W )c (G, w). If W = 2 h+1 1, then we choose k = h + 1. In this case, we have b k = W = a k = 2 h+1 1 and c  (2h + 1) (G, w). Since 2 2h+1
 (2 h+1 1) 2 , we have 2h + 1  2 log 2 (W ) and therefore we always have c  2 log 2 (W ) (G, w).

Theorem 10 implies the following corollary.

Corollary 3. There is a 2 log 2 (D)-approximation for the Spectrum Assignment problem in binary trees where D is the maximum demand.

Maximum demand at most 6

In the previous subsection, an approximation algorithm for the SA problem in binary trees where the maximum demand is at most D has been presented. This approximation is achieved by partitioning the requests into subsets of close demands. This technique is used not only in binary trees but also in general graphs as a heuristic [START_REF] Wang | Spectrum management in heterogeneous bandwidth optical networks[END_REF]. In what follows, we use di↵erent techniques to find better approximations for SA in binary trees for some given values of the maximum demand D. The techniques we use were introduced in [START_REF] Li | New approximation algorithms for some dynamic storage allocation problems[END_REF] to approximate DSA. Results in [START_REF] Li | New approximation algorithms for some dynamic storage allocation problems[END_REF] can extend directly to SA in path networks giving approximation algorithms with factors 4 3 and 1.7 when the spectrum demands are bounded by 2 and 3, respectively. In what follows we use the same techniques to design constant-factor approximations for SA in binary trees when the spectrum demand is bounded by 6.

We prove the following theorem for interval coloring.

Theorem 11. Let (G, w) be a weighted chordal graph. There are polynomial-time algorithms which find an interval coloring of (G, w) with at most Proof. As in the previous sections, (G, w) refers to the density of the weighted graph (G, w) and will be abbreviated in this proof to .

Let C(d, S) denote the set of instances of IC in which the graph is chordal, the density is at most d and the weights are in the set S. Let c(d, S) denote the smallest integer ↵ such that for each instance of C(d, S), there is an interval coloring with at most ↵ colors (if such ↵ exists).

We present first the general approach to solve the problem for any maximum weight W , before applying it to the case the case W = 3. In the appendix, as well as in [START_REF] Bermond | On Spectrum Assignment in Elastic Optical Tree-Networks[END_REF], we present the cases W 2 {3, 4, 5, 6} in detail.

General Approach. Let (G, w) be a weighted chordal graph with maximum weight W . To color the graph G, we proceed in two phases as follows.

• Partitioning the vertices into multi-level blocks: in this phase, the vertices are partitioned into blocks. We will have for each i 2 {1, . . . , W }, a set B i of n i level-i blocks B 1 i , . . . , B ni i each of density d i . The values of n i and d i will be chosen after to satisfy various conditions. We order the blocks in the lexicographic order: block B j i is before block B j 0 i 0 if i < i 0 or i = i 0 and j < j 0 . Our algorithm consists in considering successively the vertices in the RPEO order and assigning a new vertex v to the first available block (in the block's order). In more details, we assign a vertex v to a block B if the weight of the clique induced by v and its neighbors in B does not exceed the density of the block. The vertex v and its neighbors in B indeed form a clique since the graph is chordal and we consider the vertices in the RPEO order.

We will choose the parameters d i and n i (see details after) in such a way that the following property is satisfied:

Property *: Each vertex of weight i is assigned to some block in the set B l such that l  i.

In particular, this means that at the end of the algorithm each vertex is assigned to some block.

• Solving the problem of interval coloring for each block: in this second phase, the vertices of each block of B i are colored using an algorithm to solve instances with density d i and weights in S i = {i, . . . , W } (the possible weights of the vertices in B j i ). Note that the vertices of a block of B i induce a graph which belongs to C(d i , S i ). The algorithm we use is designed to use no more than c(d i , S i ) colors.

Therefore, the total number of colors used to color the whole graph is at most

W X i=1 n i c(d i , {i, . . . , W })
The total number of colors depends on n i and d i . In fact, we will proceed as follows. For a chosen set of values of the densities d i , we will choose the smallest possible n i such that Property* is satisfied. Afterwards, we will compute c(d i , {i, . . . , W }) and therefore the total number of colors for the chosen values of d i . We will do this for many values of the densities d i and keep the set of values which minimize the total number of colors.

Choice of the n i . Note that, if for some i, d i < i, then n i = 0 as a block of B i cannot be used to assign a vertex of weight < i (recall that the vertices of weight < i are by Property * all assigned to blocks of B l with l < i). So, in the following claims, we suppose d i i for all i.

Claim 1. If n 1 l d1 m
, then Property * is satisfied.

Proof. Suppose that a vertex v of weight 1 cannot be assigned to any block of B 1 . This means that, for each block B of B 1 , vertex v and its neighbors in B form a clique of size > d 1 and so the weight of the neighbors of v in B is at least d 1 . This implies that the weight of the neighbors of v in all of the blocks in B 1 is at least n 1 d 1 . Since we are considering the vertices in the RPEO, this implies that the clique induced by v and its neighbors in B 1 is of weight

n 1 d 1 + 1 which exceeds for n 1 = l d1 m . This is not possible. Claim 2. If n 2 = l 1 n1(d1 1) 2 2
m where 2 2 = max{2, d 2 1}, then Property * is satisfied.

Proof. Suppose that a vertex v of weight 2 cannot be assigned to any block of B 1 or B 2 . This means that, for each block B of B 1 (resp. B 2 ), vertex v and its neighbors in B form a clique of size > d 1 (resp. > d 2 ) and so the weight of the neighbors of v in B is at least d 1 1 (resp. d 2 1). However, if d 2 = 2, as all the vertices of weight 1 are assigned to blocks of B 1 , v has necessarily one neighbor of weight 2 in each block of B 2 . Therefore, if we let 2 2 = max{2, d 2 1}, the clique induced by v and its neighbors in the RPEO has a weight at least n

1 (d 1 1) + n 2 2 2 + 2 which exceeds for n 2 = l 1 n1(d1 1) 2 2
m .

Example: case W=2: Consider the case W = 2. We will see how the application of the claims above enables us to find another proof of the ration 3/2 already obtained inTheorem 7 and in fact a slightly better results. Let d 1 = 2and d 2 = 2. Applying the formula we get n 1 = d 2 e and

n 2 = d 1 n1 2 e.
Using the fact that c(2, {1, 2}) = c(2, {2}) = 2 the number of colors is 2n 1 + 2n 2 that is 6p for = 4p; 6p + 2 for = 4p + 1 and for = 4p + 2 and 6p + 4 for = 4p + 3 that we can express as 2 2d 1 4 e. That is slightly better than the value obtained in Theorem 7 more precisely one less when = 4p + 2 (resp. 4p + 3) where we get 6p + 2 (resp. 6p + 4) colors instead of 6p + 3 (resp. 6p + 5).

Claims 1 and 2 can be generalized as follows:

Claim 3. If n i = 2 6 6 6
+1 i i 1 P l=1 n l l i i i 3 7 7 7
where l i = max{l, d l + 1 i}, then Property * is satisfied.

Proof. Suppose that a vertex v of weight i cannot be assigned to any block of B l with l  i. This means that, for each block B of B l , vertex v and its neighbors in B form a clique of size > d l and so the weight of the neighbors of v in B is at least d l +1 i. Furthermore, as all the vertices of weight < l are assigned to blocks of B j for j < l, v has necessarily one neighbor of weight at least l in any block of B l . Therefore, if we let l i = max{l, d l + 1 i}, the clique induced by v and its neighbors in the RPEO has a weight at least .

Maximum weight 3. Let W = 3. We choose some values for d i and using the claims above, we obtain the following values of n i :

• d 1 = d 2 = d 3 = 3. n 1 = ⌃ 3 ⌥ and n 2 = ⌃ 1 2n1 2 ⌥ and n 3 = ⌃ 2 n1 2n2 3 ⌥ . • d 1 = 5, d 2 = d 3 = 3. n 1 = ⌃ 5 ⌥ and n 2 = ⌃ 1 4n1 2 ⌥ and n 3 = ⌃ 2 3n1 2n2 3 ⌥ . • d 1 = d 2 = 5, d 3 = 3. n 1 = ⌃ 5 ⌥ and n 2 = ⌃ 1 4n1 4 ⌥ and n 3 = ⌃ 2 3n1 3n2 3 ⌥ .
To compare the values of the total number of colors we need to compute c(3, S) for some basic sets S. We recall that c(d, S) is the minimum number of colors which can be used in an interval coloring of any chordal graph with density d and weights in S.

• c(3, {1, 2, 3}) = 4.
We first prove that c(3, {1, 2}) 4. Let us consider the example presented in Figure 3 in which the density is 3 and the maximum weight is 2. The graph in the example consists of a clique of 3 vertices of weight one, such that each vertex of weight one is joined to a vertex of weight 2. This graph cannot be colored using only 3 colors. If we suppose that it can be colored with 3 colors {1, 2, 3}, then one of the vertices of weight one will have to be assigned color 2. For this vertex, the neighbor of weight 2 cannot be colored since the only available colors are 1 and 3 which are not contiguous.

To prove that c(3, {1, 2, 3})  4, we use the greedy algorithm in the RPEO which needs at most 4 colors.Vertices of weight 3, if any, are isolated and can be colored with 3 colors. If a vertex v of weight 2 is considered, then v has at most one neighbor of weight 1. Let ↵ be its color. If ↵ = 1 or 2, then v can be colored with colors {3, 4}, and if ↵ = 3 or 4, then v can be colored with colors {1, 2}. If a vertex of weight 1 is considered, it has at most two neighbors of weight 1 or one neighbor of weight 2 and it can be colored with one of the two colors that are not used. In fact in an instance of C(3, {2, 3}), all vertices are isolated and we can hence easily color them with at most 3 colors.

• c(4, {1, 2, 3}) = 6.

We first prove that c(4, {1, 2, 3}) 6. Let us consider the example presented in Figure 4 which consists of a clique of four vertices of weight one. Each vertex of weight one is joined to a vertex of weight 3 and each pair of vertices of weight one is joined to a vertex of weight 2. Suppose that we only use 5 colors {1, 2, 3, 4, 5} to color this graph. If one of the vertices of weight 1 uses color 3, then its neighbor which has weight 3 cannot be colored. Otherwise, if the vertices of weight 1 use colors {1, 2, 4, 5}, then the vertex of weight 2 which is adjacent to the vertices of weight 1 which have colors 2 and 4 cannot be colored.

To color any instance in C(4, {1, 2, 3}) with at most 6 colors, we use the greedy algorithm in the RPEO. • c(5, {1, 2, 3}) = 7.

We first prove that c(5, {1, 3}) 7. Let us consider the graph G consisting of a clique of 5 vertices each of weight 1 and such that each pair of vertices of the clique is connected to a vertex of weight 3. The graph G is chordal with density 5 and weights in {1, 3}. Let us suppose that we can color G with only six colors. There are either two vertices of weight one colored with colors 2 and 4 or two vertices of weight one colored with colors 3 and 5. In both cases the vertex of weight 3 adjacent to these two vertices cannot be colored. Now let us describe an algorithm that takes an instance of C(5, {1, 2, 3}) and colors it with at most 7 colors. The algorithm is a greedy algorithm in the RPEO of the vertices with the additional feature that colors 5 and 6 are forbidden for vertices of weight 1.

- • c(5, {2, 3}) = 5.

The greedy algorithm in the RPEO in which we forbid color 3 to vertices of weight 2 uses at most 5 colors (note that a vertex of weight 3 cannot be colored with {2, 3, 4}). Now, we can compute the number of colors for the 3 cases considered above.

• the number of colors is at most + 4n 1 + 2n 2 and as n 2  4n1+2 4 it is at most 3 2 + 2n 1 + 1. Finally, as n 1  5 + 4 5 , the number of colors used is at most 19 10

+ 13 5 .
We have tried the other possible values of d i and n i but we obtained bigger numbers of colors.

Theorem 11 implies the following corollary. Corollary 4. Let I be an instance of SA in a binary tree. Let OPT be the span of I. There are polynomial-time algorithms which find a spectrum assignment for I with a span less than

Conclusion

We have studied in this article the problem of Spectrum Assignment (SA) in tree networks. We have proved that SA is NP-complete in undirected stars with 3 links and directed stars with 4 links. We have also shown that there is a 4-approximation algorithm to solve the problem in general stars. Afterwards, we have focused on SA in binary trees with special demand profiles and we have designed constant approximation algorithms for several cases. As future work, we would like to find approximation algorithms for interval coloring in chordal graphs in general and to SA in binary trees in particular. Towards this objective, we believe the following directions might be useful.

• It would be interesting to try to use the clique graph of the chordal graph [START_REF] Galinier | Chordal graphs and their clique graphs[END_REF] to find an acyclic orientation where the number of maximal cliques to which a path belongs is bounded. In fact, finding a k-approximation for interval coloring is equivalent to finding an acyclic orientation in which the longest directed path has vertices in at most k maximal cliques [START_REF] Golumbic | Algorithmic Graph Theory and Perfect Graphs[END_REF]. This approach has been used to find a 2-approximation for interval coloring in claw-free chordal graphs [START_REF] Confessore | An approximation result for the interval coloring problem on claw-free chordal graphs[END_REF].

• It would be also helpful to try to use ideas from the approximation algorithms used for interval coloring in interval graphs. These algorithms were developed for the problem of Dynamic Storage Allocation (DSA) as we mentioned in Section 2.2.3 and they use mainly three techniques:

-2-coloring (2-allocation) [START_REF] Gergov | Algorithms for compile-time memory optimization[END_REF]: in this technique, which yields a 3-approximation for Interval Coloring (IC) in interval graphs, first, a 2-coloring is found where 2 adjacent vertices but not three might use the same color. This 2-coloring is transformed afterwards to a normal coloring. Is it possible to find a 2-coloring for chordal graphs in polynomial time?

-Boxing vertices [START_REF] Buchsbaum | Opt versus load in dynamic storage allocation[END_REF]: in this technique, which yields a 2 + ✏ approximation for IC in interval graphs, vertices are modeled as rectangles (the dimensions of a rectangle corresponding to a vertex v are the weight of v and the interval corresponding to v in the interval representation of the graph). These rectangles are cleverly boxed or gathered in larger rectangles. Afterwards an exact algorithm is used to color these large rectangles. Is it possible to adapt such technique to chordal graphs and find a clever way to box the vertices?

-Buddy-decreasing-size algorithm [START_REF] Chrobak | On some packing problem related to dynamic storage allocation[END_REF]: in this algorithm, which yields a 6-approximation for IC in interval graphs, vertices are colored in the decreasing order of their weights. Some of the challenges in this direction is that using it as it is for chordal graphs cannot give better than a log(n)-approximation; there is a tight example in [START_REF] Pemmaraju | Approximating interval coloring and max-coloring in chordal graphs[END_REF]. In the tight example however all the vertices have the same weight which means that there is an exponential number of possible orders. Is there a clever order (something similar to lexicographic order?) which can give a better approximation ratio?

Finally the case of SA in general trees remains a challenging problem. Perhaps the case of trees with maximum degree 4 can be studied by using the fact that the conflict graph of these instances of SA are in that case weakly chordal.

• c(6, {1, 2, 3, 4}) = c(6, {1, 2, 3}) = 9.

We first prove that c(6, {1, 3}) 9. Let us consider the graph G consisting of a clique of 6 vertices of weight 1 each and such that the vertices of each triple of the clique are connected to a vertex of weight 3. The graph G is chordal with density 6 and weights in {1, 3}. Let us suppose that we can color G with only 8 colors. There are three vertices of weight 1 using colors {1, 4, 7} or three vertices of weight 1 using colors {2, 5, 8} or two vertices of weight 1 using colors {3, 6}. In any of these three cases, a vertex of weight 3 cannot be colored. it is at most 16 9 + 22 9 n 1 + 4 9 .

• c(7, {1, 2, 3, 4, 5})  12.

To obtain a coloring with 12 colors, we use the greedy algorithm in the RPEO with the additional feature of forbidding colors {8, 9, 10, 11, 12} to vertices of weight 1 and colors {8, 9} and {9, 10} for vertices of weight 2. The proof that the algorithm works is done by considering the various possibilities when a new vertex is added.

-If a vertex v of weight 5 is considered, then if v has:

⇤ 2 neighbors

Figure 1 :

 1 Figure 1: Example of an instance of SA and its associated conflict graph

Figure 2 :

 2 Figure 2: Reduction from 2-PARTITION to SA in a directed star

1 For

 1 S ✓ V , we define G[S] as the subgraph of G induced by the vertices of S, i.e. the subgraph of G containing the vertices of S and all the edges of G which have both endpoints in S.

Figure 3 :

 3 Figure 3: An example showing that c(3, {1, 2}) 6 = 3

Figure 4 : 5 • c( 4 ,

 454 Figure 4: An example showing that c(4, {1, 2, 3}) 6 = 5

2 it is at most 3 2 + 6 + 4 3 .• 8 5 .•

 2264385 If we set d 1 = d 2 = d 3 = 3, the number of colors used is n 1 c(3, {1, 2, 3}) + n 2 c(3, {2, 3}) + n 3 c(3, {3}) = 4n 1 +3n 2 +3n 3 . As n 3  n1 2n2 3 the number of colors is at most +3n 1 +n 2 and as n 2  2n1 2n 1 . Finally, as n 1  3 + 2 3 , the number of colors used is at most 13 If we set d 1 = 5, d 2 = d 3 = 3, the number of colors used is n 1 c(5, {1, 2, 3}) + n 2 c(3, {2, 3}) + n 3 c(3, {3}) = 7n 1 +3n 2 +3n 3 . As n 3  3n1 2n2 3 the number of colors is at most +4n 1 +n 2 and as n 2  4n1 2 it is at most 3 2 + 2n 1 . Finally, as n 1  5 + 4 5 , the number of colors used is at most 19 10 + If we set d 1 = d 2 = 5, and d 3 = 3, the number of colors used is n 1 c(5, {1, 2, 3}) + n 2 c(5, {2, 3}) + n 3 c(3, {3}) = 7n 1 + 5n 2 + 3n 3 . As n 3  3n1 3n2 3

- 6 ⌥ ; n 2 = ⌃ 1 5n1 3 ⌥ ; n 3 = ⌃ 2 4n1 2n2 3 ⌥ , and n 4 = ⌃ 3 3n1 2n2 3n3 4 ⌥ . As n 4 

 62333444 If a vertex v of weight 2 is considered. If all its neighbors that have been already colored are of weight 1, then v can be assigned colors {7, 8}. If v has two colored neighbors of weight 2 each, or one colored neighbor of weight 2 and two other colored neighbors with weight 1, or one colored neighbor of weight 3 and another of weight 1, or one vertex of weight 4, then one of the channels {1, 2}, {3, 4}, {5, 6}, or {7, 8} is necessarily free to be used.• c(6, {2, 3, 4}) = 8.We first prove that c(6, {2, 4}) 8. Let us consider the graph G which consists of a clique of 3 vertices of weight 2 each, and such that each vertex of weight 2 is connected to a vertex of weight 4. The graph G is chordal and has density 6 and weights in {2, 4}. Let us suppose that we can color G with only 7 colors. In any possible coloring of the vertices of weight 2, a vertex v of weight 2 has to use either colors {3, 4} or {4, 5}. In both cases, the neighbor of v which has weight 4 cannot be colored. Now let us describe the algorithm that colors an instance of C(6, {2, 3, 4}). It is a greedy algorithm in the RPEO with the additional feature that the possible combinations of colors for vertices of weight 2 are the following: {1, 2}, {3, 4}, {5, 6}, and {7, 8}.• c(6, {3, 4}) = 6.Vertices of weight 4 are isolated and can be all assigned colors {1, 2, 3, 4} and other vertices can be colored using the greedy algorithm in the RPEO with at most 6 colors. Now, we can compute the number of colors for d 1 = 6 and d 2 = d 3 = d 4 = 4. The number of colors used is n 1 c(6, {1, 2, 3, 4})+n 2 c(4, {2, 3, 4})+n 3 c(4, {3, 4})+n 4 c(4, {4}) = 9n 1 + 4n 2 + 4n 3 + 4n 4 . We have n 1 = ⌃ 3n1 2n2 3n3 4 the number of colors is at most +6n 1 +2n 2 +n 3 . As n 3  4n1 2n2 3 the number of colors is at most 4 3 + 14 3 n 1 + 4 3 n 2 , and as n 2  5n1+1 3

  If a vertex v of weight 3 is considered, then if v has a neighbor of weight 2 colored with {↵, ↵ + 1}, we color v with {1, 2, 3} if ↵ 4 or {5, 6, 7} if ↵  3. If v has two neighbors of weight 1; if color 7 is not used we color v with {5, 6, 7}. If color 7 is used, but not color 4 we color v with {4, 5, 6}. If both colors 4 and 7 are used, we color v with {1, 2, 3}. -If a vertex v of weight 2 is considered, then if v has 3 neighbors of weight 1, we color v with {5, 6}. If it has one neighbor of weight 2 colored {↵, ↵ + 1} and one of weight 1 colored , then we color v with {5, 6} if ↵  3; with {1, 2} if ↵ 4 and 3; with color {6, 7} if ↵ = 4 and  2 or {3, 4} if ↵ 5 and  2.

  Now let us describe an algorithm that takes an instance of C(6, {1, 2, 3, 4}) and colors it with at most 9 colors. The algorithm is a greedy algorithm in the RPEO of the vertices with two additional features: colors 6,7 and 8 are forbidden to vertices of weight 1, and each vertex of weight 2 is assigned colors {1, 2}, {3, 4}, {5, 6}, or {7, 8} and not any other contiguous combination of two colors. This algorithm uses at most 9 colors.-If a vertex v of weight 4 is considered, then if v has a neighbor of weight 2 which has been already colored, the possible sets of color used by this neighbor are {1, 2}, {3, 4}, {5, 6}, or {7, 8}. In any case, v can be colored with 4 contiguous colors. If v has two neighbors of weight 1 each that have been already colored, then either one of the colors 9 or 5 is not used by this neighbor, and in this case v can use it along with the colors {6, 7, 8} (which are forbidden for vertices of weight 1), or both colors 9 and 5 are used and v can use colors {1, 2, 3, 4}. {1, 2, 3} if ↵ = 5 or 7 and 4; {7, 8, 9} if ↵ = 5 and  3; {4, 5, 6} if ↵ = 7 and  3.

-If a vertex v of weight 3 is considered, then if v has a neighbor of weight 3 colored with {↵, ↵ + 1, ↵ + 2}, we color v with {1, 2, 3} if ↵ 4 or with {7, 8, 9} if ↵  3. If v has two neighbors one of weight 2 colored with {↵, ↵ + 1} and one of weight 1 colored with , then we color v with {6, 7, 8} if ↵ = 1 or 3;

  of weight 1, we color v with {8, 9, 10, 11, 12}. ⇤ 1 neighbor of weight 2 colored with {↵, ↵ +1}, we color v with {1, 2, 3, 4, 5} if ↵ 6or with {8, 9, 10, 11, 12} if ↵  5.-If a vertex v of weight 4 is considered, then if v has:⇤ 3 neighbors of weight1, we color v with {9, 10, 11, 12}. ⇤ 1 neighbor of weight 2 colored with {↵, ↵ + 1} and 1 neighbor of weight 1 colored , we color v with {9, 10, 11, 12} if ↵  7; otherwise ↵ 10 and we color v with {1, 2, 3, 4} if 5 or with {5, 6, 7, 8} if  4 (Note that we use the fact that ↵ 6 = 8; otherwise with ↵ = 8 and = 4 we could not have colored v). ⇤ 1 neighbor of weight 3 colored with {↵, ↵ + 1, ↵ + 2}, we color v with {1, 2, 3, 4} if ↵ 5 or {9, 10, 11, 12} if ↵  4. -If a vertex v of weight 3 is considered, then if v has: ⇤ 4 neighbors of weight 1, we color v with {10, 11, 12}. ⇤ 1 neighbor of weight 2 colored with {↵, ↵ + 1} and 2 neighbors of weight 1 colored < , we color v with {10, 11, 12} if ↵  7; otherwise ↵ 10, and we color v with {1, 2, 3} if 4 or with {4, 5, 6} if  3 and 7 or with {7, 8, 9} if  3 and  6. (Note that we use the fact that ↵ 6 = 9; otherwise with ↵ = 9, = 3 and = 6 we could not have colored v). ⇤ 2 neighbors of weight 2 colored with {↵, ↵ + 1} { , + 1} with ↵ < , we color v with {1, 2, 3} if ↵ 4, or with {5, 6, 7} if ↵  3 and 10, or with {10, 11, 12} if ↵  3 and  7. ⇤ 1 neighbor of weight 3 colored with {↵, ↵ + 1, ↵ + 2} and 1 neighbor of weight 1 colored , we color v with {10, 11, 12} if ↵  7 or {1, 2, 3} if ↵ 8 and 4 or with {4, 5, 6, } if ↵ 8 and  3. ⇤ 1 neighbor of weight 4 colored with {↵, ↵ + 1, ↵ + 2, ↵ + 3}, we color v with {1, 2, 3} if ↵ 4 or {10, 11, 12} if ↵  3. -If a vertex v of weight 2 is considered, then if v has: ⇤ 5 neighbors of weight 1, we color v with {11, 12}. ⇤ 1 neighbor of weight 2 colored with {↵, ↵ + 1} and 3 neighbors of weight 1 colored < < , we color v with {11, 12} if ↵  7; otherwise if ↵ 10 we color v with {1, 2} if 3, or with {3, 4} if  2 and 5, or with {5, 6} if  2,  4 and 7, or with {7, 8} if  2,  4 and  6. ⇤ 2 neighbors of weight 2 colored with {↵, ↵ + 1} and { , + 1} with ↵ < , and a neighbor of weight 1 colored , we color v with {11, 12} if  7; otherwise if 10 we color v with {1, 2} if ↵ 3 and 3, or with {4, 5} if ↵  2 and 6, or with {6, 7} if ↵  2 and  5, or with {3, 4} if ↵ 5 and  2, or with {6, 7} if ↵  4 and  2. ⇤ 1 neighbor of weight 3 colored with {↵, ↵ + 1, ↵ + 2} and 2 neighbors of weight 1 colored < , we color v with {11, 12} if ↵  8; otherwise if ↵ 9 we color v with {1, 2} if 3 or with {4, 5} if  2 and 6 or with {6, 7} if  2 and  5.

⇤ 1 neighbor of weight 3 colored with {↵, ↵ + 1, ↵ + 2} and 1 neighbor of weight 2 colored { , + 1}, we color v with {1, 2} if ↵ 3 and 3, or with {11, 12} if ↵  2 and  7, or with {5, 6} if ↵  2 and 10, or with {4, 5} if ↵ 6 and  2, or with {11, 12} if ↵  5 and  2.

Acknowledgment: We thank the referees for their comments and pieces of advices which helped to improve the paper.

I

This work has been partly supported by ANR project Stint under reference ANR-13-BS02-0007, ANR program "Investments for the Future" under reference ANR-11-LABX-0031-01, and a grant from the "Conseil régional Provence Alpes-Côte d'Azur".

Appendix for the reviewers

We include in this appendix the parts of the proof of Theorem 11, which we have omitted from the paper. These proofs can also be found in [START_REF] Bermond | On Spectrum Assignment in Elastic Optical Tree-Networks[END_REF].

Maximum weight 4. Let us first compute c(4, S) for some basic sets S.

• c(4, {1, 2, 3, 4}) = 6.

Since in an instance of C(4, {1, 2, 3, 4}), the vertices of weight 4 are isolated, we color them and then use the algorithm used to prove that c(4, {1, 2, 3}) = 6 to color the other vertices.

• c(4, {2, 3, 4}) = 4.

A greedy algorithm in the RPEO uses at most 4 colors. In fact, in an instance of C(4, {2, 3, 4}), vertices of weights 3 or 4 are isolated and it su ces to color vertices of weight 2 with {1, 2} or {3, 4}.

• c(4, {3, 4}) = c(4, {4}) = 4.

In an instance of C(4, {3, 4}), all vertices are isolated and can be colored independently.

• c(5, {1, 2, 3, 4}) = 8.

We first prove that c(5, {1, 2, 3, 4}) 8. Let us consider the graph G which consists of a clique of 5 vertices of weight 1 each and such that each vertex of weight one is connected to a new vertex of weight 4 and each pair of vertices of weight 1 is connected to a new vertex of weight 3. The graph G is chordal and has density 5 and maximum weight 4. Suppose that only 7 colors can be used to color G. Color 4 cannot be used for any vertex of weight 1, otherwise its neighbor of weight 4 cannot be colored. Furthermore we can use for vertices of weight 1 at most one of the pair of colors {2, 5} and {3, 6}, otherwise the neighbor of weight 3 connected to this pair cannot be colored. So we have altogether 3 colors forbidden for vertices of weight 1 and so only 4 available colors which is impossible. Now let us describe an algorithm that takes an instance of C(5, {1, 2, 3, 4}) and colors it with at most 8 colors. The algorithm uses the greedy algorithm in the RPEO with the additional feature that colors 3 and 6 are forbidden to vertices of weight 1. Let us check that this algorithm uses indeed at most 8 colors.

-If a vertex v of weight 4 is considered, then if v has a neighbor of weight [START_REF] Beauquier | Communication dans les réseaux optiques par multiplexage en longueur d'onde[END_REF] • c(5, {2, 3, 4}) = 5.

In an instance of C(5, {2, 3, 4}), vertices of weight 4 are isolated. We can color them then all with colors {1, 2, 3, 4}. For the vertices of weights 2 and 3, we use the algorithm which achieves c(5, {2, 3}) = 5.

Finally, as n 1  +5 6 , the number of colors is at most 59 27 + 67 27 .

We have computed the number of colors for other choices of the d i but the values are bigger. For maximum weight 4, we obtain an approximation with a multiplicative ratio of 59 27 and an additive constant of 67 27 .

Maximum weight 5. Let us first compute c(5, S) for some basic sets S.

• c(5, {1, 2, 3, 4, 5}) = 8.

In fact, we know that c(5, {1, . . . , 4}) = 8 and for any chordal graph with density 5 and maximum weight 5, vertices of weight 5 are isolated and can be colored independently from the others.

• c(5, {2, 3, 4, 5}) = 5.

In a chordal graph of density 5 and weights in {2, . . . , 5}, vertices of weight 4 or 5 are isolated and can be easily colored. For other vertices, we know that c(5, {2, 3}) = 5.

• c(5, {3, 4, 5}) = c(5, {4, 5}) = 5.

All vertices are isolated and can be easily colored.

• c(6, {1, 2, 3, 4, 5}) = 10.

We first prove that c(6, {1, . . . , 5}) = 10. Let us consider the graph G which consists of a clique C of 6 vertices of weight 1 such that each of the vertices of C is connected to a vertex of weight 5, and each pair of vertices of C is connected to a vertex of weight 4. Let us suppose that we can color G with 9 colors. Color 5 cannot be used for any vertex of weight 1, otherwise its neighbor of weight 5 cannot be colored. Furthermore we can use for vertices of weight 1 at most one of the pair of colors {2, 6}, {3, 7}, {4, 8}, otherwise the neighbor of weight 4 connected to this pair cannot be colored. So we have altogether 4 colors forbidden for vertices of weight 1 and so only 5 available colors which is impossible.

The greedy algorithm in the RPEO with the additional feature of forbidding colors {7, 8, 9, 10} to vertices of weight 1 colors any instance of C(6, {1, . . . , 5}) with at most 10 colors.

• c(6, {2, 3, 4, 5}) = 8. Vertices of weight 5 are isolated and can be easily colored. As for other vertices we have already proved that c(6, {2, 3, 4}) = 8.

• c(6, {3, 4, 5}) = 6. Vertices of weight 4 and 5 are isolated and vertices of weight 3 can be colored using the greedy algorithm in the RPEO with either the colors {1, 2, 3} or {4, 5, 6}. We have

, and

As in the preceding cases, we, successively, use upper bounds for the n i . The number of colors is at most + 9n 1 + 3n 2 + 2n 3 + n 4 , then 5 4 + 8n 1 + 5 2 n 2 + 5 4 n 3 , then We have computed the number of colors for other choices of the d i but we obtained bigger values as we present in what follows. For maximum weight 5, we obtain an approximation with a multiplicative ratio of 859 336 and an additive constant of 229 56 .

Maximum weight 6. Let us first compute c(6, S) for some basic sets S. Note that with a density at most 6, any vertices of weight 6 are isolated. We can then deduce the following from what we have computed for a maximum weight of 5.

• c(6, {1, 2, 3, 4, 5, 6}) = 10.

• c(6, {2, 3, 4, 5, 6}) = 8.

• c(6, {3, 4, 5, 6}) = c(6, {4, 5, 6}) = c(6, {5, 6}) = c(6, {6}) = 6.

• c(7, {1, 2, 3, 4, 5, 6}) = 12.

We use the algorithm which gives c(7, {1, 2, 3, 4, 5, })  12. If a vertex v of weight 6 is added it is joined to at most one vertex of weight 1 of color . If  6, we color v with colors {7, 8, 9, 10, 11, 12}) and if = 7 with colors {1, 2, 3, 4, 5, 6}) and so c(7, {1, 2, 3, 4, 5, 6})  12.

To show that c(7, {1, 2, 3, 4, 5, 6}) 12, we consider the chordal graph consisting of a clique of 7 vertices of weight one such that each vertex of this clique is joined to a vertex of weight 6. Furthermore we join each pair of vertices of weight 1 to a vertex of weight 5. Suppose that we can color the graph with 11 colors. Color 6 cannot be used for any vertex of weight 1, otherwise its neighbor of weight 6 cannot be colored. Furthermore we can use for vertices of weight 1 at most one color of each of the following pairs of colors {2, 7}, {3, 8}, {4, 9}, {5, 10}, otherwise the neighbor of weight 5 connected to this pair cannot be colored. So we have altogether 5 colors forbidden for vertices of weight 1 and so only 6 available colors which is impossible. We have

, and n 6 = ⌃ 5 2n1 2n2 3n3 4n4 5n5 6 ⌥ . Like in the preceding cases, we obtain upperbounds on n i . The number of colors is at most +10n 1 +6n 2 +3n 3 +2n 4 +n 5 , then 1). We could improve the value if we could prove that c(8, {1, 2, 3, 4, 5, 6})  14 but that seems not possible. We can only prove c(8, {1, 2, 3, 4, 5, 6})  15 which gives a bigger number of colors.

For maximum weight 6, we obtain an approximation with a multiplicative ratio of 287 100 and an additive constant of 885 200 .