Chapter 10
Graph Coloring Problems 1
We present the basic concepts of colorings as well as a series of variations and generalizations prompted by various scheduling problems including drawing up school timetables. A few recent exact algorithms and some heuristics will be presented. In particular we will give an outline of methods based on the Tabu search for finding approximate solutions for large problems. Lastly, we mention application of colorings to various problems, including computer file transfers and production systems. This text is an extended version of [WER 03].
10.1. Basic notions of colorings
Let us consider a business that uses n chemical products p1,…, pn for its manufacturing process, and must store them before using them. From the nature of these products, a list of constraints that indicates which pairs [pi, pj] of products cannot be stored together in the same storage compartment must be adhered to.
A natural question is then to establish what is the minimum number of storage compartments that we need to use to store the chemical products in safety (ignoring the constraints of the size of the various storage compartments). This question can be formulated in terms of graph coloring in the following way. With each of the n chemical products pi we associate a vertex pi of a simple graph G, and with each couple pi, pj of products that cannot be stored together, we make a corresponding edge [pi, pj] of this graph. The problem of establishing the smallest number of compartments then consists of finding the smallest integer k that allows us to assign to each product pi a compartment c(i) from the set I = {1,…, k}, while having c(i) ≠ c(j) for every edge [pi, pj] of G. This precisely represents a coloring of the vertices of the graph G.
Let us now consider a problem that at first seems very different: let there be a collection X = {x1,…, xn} of tasks of the same duration to be executed, while satisfying a series E of constraints that specify that certain couples [xi, xj] of tasks cannot be executed simultaneously.
If we assume that each task is indivisible and lasts exactly one day, we may ask ourselves if it is possible to execute all the tasks in a given interval I of k days while satisfying the constraints, or what is the smallest interval of time necessary for the execution of all the tasks.
These are, once again, questions which can be formulated in terms of coloring: let us associate a vertex xi of a simple graph G with each task xi from the collection X, and with each couple xi, xj of tasks linked by a constraint of non-simultaneity (we call this a disjunction constraint), we make a corresponding edge [xi, xj] of this graph which will be denoted by G = (X, E). If the set of days of the interval I is made up of days 1, 2,…, k then the first question comes down to asking whether it is possible to assign to each task xi an execution day c(i) chosen from the set {1, 2,…, k} in such a way that for every couple of tasks associated with an edge [xi, xj] of E we have c(i) > c(j) or c(j) > c(i). In other words, c(i) ≠ c(j). This is once again a coloring (of the vertices) of the graph G.
Thus a coloring of a simple graph G = (X, E) is the assignment to each vertex xi of X of a color c(i) in such a way that for every edge [xi, xj] of E we have c(i) ≠ c(j). We refer to a k-coloring of a graph if the set I of the usable colors is of cardinality k.
As for the questions of establishing the smallest set I of storage compartments for the chemical products, and of finding out which is the smallest interval I of days that allows us to execute all the tasks, they come down to finding the smallest k = |I| for which the corresponding graph G allows a k-coloration; this is the chromatic number χ(G) of the graph G.
From habit, we talk about graph coloring, when very often – and this is the case for the examples above – we use (non-negative) integers c(i) instead of colors; we should therefore talk about “numbering”. The use of a set I = {1,…, k} of integers instead of colors allows us to see the links that exist between the colorings and the orientations of a graph. The set I is indeed ordered and we can formulate property 10.1.
PROPERTY 10.1.– A graph G = (X, E) allows a k-coloring if and only if we can direct each edge of G in such a way as to obtain a directed graph H without any circuits and without any paths that encounter more than k vertices.
Proof. If G has a k-coloring that uses the colors 1, 2,…, k then for every edge [xi, xj] we choose the direction xi → xj if c(i) < c(j) or xi ← xj if c(i) > c(j). The graph H obtained is of the desired form. Inversely, if a graph H has such an orientation, we associate a value c(i) equal to the number of vertices encountered on the longest path that ends with each vertex xi; we can easily verify that the c(i) defined are a k-coloring of the graph G obtained by removing the directions in H.
It is interesting to note that the question of whether a k-coloring of a simple graph G = (X, E) exists can be reduced to the question of whether a stable set of |X| vertices exists in an auxiliary graph 
. This observation will be used later when we deal with coloring problems with colors forbidden for certain vertices.
Let us assume therefore that we have to establish whether the graph G = (X, E) allows a k-coloring (fixed k). We associate with G an auxiliary graph 
obtained by introducing k copies G1,…, Gk of the graph G: each vertex a of G corresponds to a vertex ai of Gi and we link ai, bi with an edge [ai, bi] if [a, b] is an edge of G. Lastly, for every vertex a of G, we link the corresponding vertices a1,…, ak in such a way as to form a clique. The construction is illustrated in Figure 10.1.
Figure 10.1. Reducing coloring to a stable set problem
There is a one-to-one mapping between the k-colorings of G and the stable sets of 
with |X| vertices. Let S be such a stable set of 
; we deduce a k-coloring from this using the following rule: if ai ∈ S then a has the color i in the coloring. Similarly, from a k-coloring of G, we construct a stable set of |X| vertices in G: if the vertex a has the color i then ai ∈ S. In Figure 10.2, we use this construction to examine whether a graph has a k-coloring.
Figure 10.2. An attempt to color G with k = 2 colors
This transformation of the k-coloring problem into a stable set problem is also useful for solving the following question, which has applications in certain scheduling problems: what is the maximum number of vertices of a given graph G that we can color using a fixed number k of colors? This problem is solved by finding a stable set of maximum size in 
; in timetable terms, this comes down to asking what is the maximum number of tasks in the given collection that we are able to execute in an interval of k days.
While we do not generally know any combinatorial algorithm for processing directly in terms of colors, formulating in terms of stable sets allows us to turn to maximum cardinality stable set construction algorithms (exact or heuristic).
10.2. Complexity of coloring
The problem of establishing the chromatic number is hard. More exactly, establishing whether a given graph has a k-coloring for a fixed k > 2 is NP-complete [GAR 76b]. Furthermore, finding out whether a (2 – ε)χ(G)-coloring of a graph G exists for every ε > 0 is also NP-complete [GAR 76a].
If A(G) is the number of colors used by a polynomial algorithm A to color a graph G = (X, E), it is not possible to have systematically:
for ε > 0 [BEL 98]. However, a well-chosen polynomial algorithm A″ allows us to have, for a constant c [HAL 93]:
Classes of graphs exist for which the chromatic number can be better approximated in polynomial time. For example, in the special case where G is a planar graph (that is a graph that we can represent in the plane without any edges crossing each other), we can show that χ(G) 
5 [BER 83]. In fact, it is even possible to show that χ(G) 4, but the known proofs are arduous.
Various notions even allow us to obtain classes of graphs for which the chromatic number can be established in polynomial (in the size of the graph) time. An early example of such a notion is that of perfection, which gives rise to the well-known class of perfect graphs that we will see later. Another notion is that of “clique-width”. The clique-width of a graph G, represented by cwd(G), is the minimum number of labels needed to construct G with the following four operations: creating a new vertex with a certain label, disjoint union, connecting vertices with certain labels, and relabeling [COU 93]. An algebraic expression that represents constructing a graph G with these four operations is called a k-expression, where k is the number of labels used. It has been proven that the chromatic number problem can be solved in polynomial time on graph classes with a “clique-width” that is bounded by a constant k, as long as a k-expression can be found in polynomial time [KOB 03]. The notion of clique-width still being relatively new, the number of such classes known (especially classes that are not subclasses of perfect graphs) is still low, but growing regularly (see [INS] for a few classes of this type).
More generally, the chromatic number of a graph can be established by applying an exact algorithm, if the graph is not too large. Otherwise, we content ourselves with estimating the chromatic number, for example by using a heuristic algorithm which will only give an upper bound, but which is a lot quicker than an exact algorithm.
10.3. Sequential methods of coloring
If ω(G) is the maximal size of a clique (that is a set of vertices that are all joined pairwise) of G, it is easy to be persuaded that χ(G) 
ω(G). Unfortunately, ω(G) can be a lower bound of poor quality; indeed, it is possible to construct graphs G that do not contain any cliques of size three (therefore ω(G) 2), and with a value of χ(G) arbitrarily large. Other lower bounds can be found in [BER 83], for example:
for a graph G with n vertices and m edges.
Another way of estimating χ(G) consists of finding upper bounds. For this, it suffices to find colorings. Here we present a few simple coloring methods, based on the following sequential coloring algorithm:
Sequential coloring algorithm:
find an order 
= (x1, x2,…, xn) of the vertices of G
for i := 1 to n do
give the smallest color possible to xi
– – that is to say the smallest color which is
– – not used by xj adjacent to xi for every j < i
end for
This very general method is a sequential algorithm based on the order . The order used obviously affects the number of colors used, but we have property 10.2.
PROPERTY 10.2.– For every graph G, there exists an order of the vertices for which the sequential algorithm based on the order provides a coloring in χ(G) colors.
Proof. To persuade ourselves that such an order exists, let us consider a k-coloring of G with k = χ(G). It is then sufficient to create an order in which the vertices of color 1 precede those of color 2, which themselves precede those of color 3, and so on.
The difficulty of the coloring problems lies in the fact that such an order can be hard to find. In the special case of graphs without P4 (that is that do not contain the structure in Figure 10.3), any order of the vertices allows the sequential algorithm to obtain a coloring with the minimum number of colors.
Figure 10.3. Graph P4
We will express by Δ(G) the maximum degree of G, that is the maximum number of edges that are adjacent to any one vertex of G. The sequential algorithm (the vertex to be colored is given the smallest color available) ensures that the total number of colors used does not exceed Δ(G) + 1, whatever the order = (x1, x2,…, xn). Thus, χ(G) Δ(G) + 1 for every graph G. By following the same reasoning, we can be more precise: if Gi is the subgraph of G induced by x1,…, xi and dH(x) the number of neighbors of x in H, we have property 10.3.
With the aim of obtaining the best possible bound, we may wish to find an order = (x1, x2,…, xn) such that 
is as small as possible. But the values 
are not known in advance. This is why we prefer the bound:
which stems from the previous property because 
. This bound is minimized by using an order = (x1,x2,…,xn) such that dG(x1) dG(x2) … dG(xn) [WEL 67].
Various other methods for choosing {O} have been proposed in the literature. The best ones are dynamic, that is they do not fix this order completely from the start. One of the most effective is RLF (for recursive largest first), presented in [LEI 79], which works in the following way. The first vertex x1 is a vertex of maximal degree, and is given the color 1. Let us then assume that i vertices (x1,…, xi) have been given color 1. Now let N0 (or N1 respectively) be the set of the non-colored vertices not adjacent to any (or at least to one respectively) colored vertex; the vertex xi+1 is chosen from among the vertices x of N0 maximizing 
. This is repeated until N0 is empty. The process is then iterated with color 2 on the graph generated by the non-colored vertices, and so on, until all the vertices have been given a color.
Sequential algorithms have the advantage of speed (a few seconds of calculation on a computer for graphs with several hundred, or even several thousand vertices), but in general use more colors than necessary. On the other hand, exact algorithms allow us to establish χ(G), but necessitate very large computation times (if we restrict ourselves to one day’s calculation on a computer, it is currently barely possible to consider random graphs of more than 120 vertices).
10.4. An exact coloring algorithm
The only known way of establishing the chromatic number of a graph G is to (implicitly) enumerate all the colorings of G. In general, we start by considering an upper bound q on χ(G); this can be obtained with the help of a sequential algorithm or, even better, by applying the Tabu search described later.
We then color G using the sequential algorithm based on an order x1,…, xn; if color q has not been used, we have obtained a coloring in q1 < q colors. So we replace q with q1 and go back in the sequential algorithm (by decoloring the vertices) to the vertex xr such that xr+1 was the first vertex to be given the color q1. We recolor xr with the smallest possible color that is larger than its current color, and we continue the sequential algorithm with xr+1,…, xn. If at any given time the color q must be assigned to a vertex xs (which we want to avoid, since we would like to use less than q colors), we go back in the sequential algorithm until xs−1 and we do as before (that is we recolor xs−1 with the smallest possible color that is larger than its current color and we continue). The algorithm stops when we have gone back to x1, and χ(G) is equal to the current value of q.
Certain points of this method can be improved to give the EPCOT algorithm [DUB 93] described below. Here, the first vertices x1,…, xg are chosen in such a way as to form a clique, and the order of the remaining vertices is modified dynamically on the basis of the degree of saturation of the vertices (for a vertex x and a partial coloring, the degree of saturation is the number of colors adjacent to x). A third adaptation takes into account the following observation: if c is the largest color used among the vertices x1,…, xp, it is pointless trying colors larger than c + 1 for xp+1 (we can always exchange two colors in a coloring).
The EPCOT algorithm has a graph G = (X, E) as input and provides its chromatic number χ(G). The variables used are the number m of colored vertices, the current vertex s, the cardinality g of the initial clique, and the four vectors degree (which contains the degree of each vertex), color (the current (partial) coloring), dsat (which contains the degree of saturation of the vertices induced by the current coloring), and order (where order[j] is the vertex that has been colored in the j-th position). The EPCOT algorithm is as follows:
By “an inclusionwise maximal clique”, we mean a clique K such that there does not exist any clique larger than K′ that entirely contains K. Such a clique is easy to find since it is sufficient to start from any clique and add a vertex that is adjacent to all the vertices of the current clique while such a vertex exists. Using a more sophisticated method may allow us to find larger cliques, and therefore to reduce the execution time of EPCOT slightly.
Another interesting approach to improving the basic exact algorithm is based on the notion of critical graphs; we call a graph G for which all the proper induced sub-graphs (that is different from G itself) have a chromatic number less than χ(G) critical. It is clear that every (non-critical) graph G contains an induced critical subgraph G′ such that χ(G) = χ(G″). In order to calculate χ(G), we can seek to determine a critical subgraph G″ (which, if possible, has few vertices) such that χ(G) = χ(G′), and we will apply an exact procedure for finding the chromatic number to G′ rather than to G.
If, as in [HER 02], we denote an exact algorithm for finding χ(G) by EX, and a heuristic method that produces an upper bound H(G) on χ(G) by H, we can formulate the exact algorithm in the following way:
EX algorithm:
It is easy to see that if k is an upper bound on χ(G), and if G″ is an induced subgraph of G, then in the case where χ(G′) = k, we also have χ(G) = χ(G″). Furthermore, if G″ is the graph obtained at the end of step 2, then in the case where χ(G″) = H(G), G′ is critical and satisfies χ(G″) = χ(G).
Lastly, we observe that in step 3 we calculate χ(G″); it follows that if χ(G″) = H(G) then χ(G) = H(G) and the algorithm stops. If all the upper bounds calculated by the algorithm H in steps 1 and 2 are equal to the chromatic numbers of the graphs concerned then the algorithm stops at step 3.
But it is possible that we have χ(G″) < H(G); in this case, we start an augmenting phase where we add vertices to G″ until we have χ(G″) = H(G) or G″ = G.
This augmenting proceeds as follows: given an induced subgraph G″ of G, we consider each vertex x which is in G but not in G″ and we calculate an upper bound H(G″+x) on χ(G″+x); if H(G″+x) > χ(G″), it is possible that we have χ(G″+x) = χ(G″)+1; in this case we apply the exact algorithm EX to G″+x to attempt to confirm this.
If we have χ(G″ + x) = χ(G″) + 1 then we insert x into the list. At the end of step 4, each vertex x that is found in the list is such that χ(G″ + x) = χ(G″) + 1, while each other vertex x that is in G but not in G′ satisfies χ(G″ + x) = χ(G″).
In step 5, we add a vertex x into G″; if the list is not empty then we choose x from this list and we increase the chromatic number by 1. Otherwise every vertex of G−G″ is added to G″ without increasing the chromatic number.
This algorithm, along with a few improvements, is described in [HER 02], where the performance is also evaluated. The best results are obtained when we construct an order of the vertices for step 2 dynamically by choosing the vertex of G″ of minimum degree each time.
In the augmenting phase, it is also worthwhile choose an order for adding the vertices from the list into G″; choosing the vertex with the greatest number of neighbors in G″ gives the best results.
10.5. Tabu search
Because of the calculation time, it is not possible to use an exact algorithm to determine the chromatic number of a graph of reasonable size (that is beyond 120 vertices); we must be satisfied with finding an upper bound on it. While sequential algorithms based on orders have the advantage of speed, in general they provide a very large upper bound for graphs that have more than a few hundred vertices. This is why more effective heuristic algorithms have been proposed. The one that we describe here is an adaptation of the Tabu search (described in more detail in [GLO 97]) to the problem of establishing a k-coloring.
In this algorithm, a solution is simply a partition s = (X1,…, Xk) of the set of the vertices X of the graph G = (X, E) to be colored. Such a partition is a k-coloring if and only if no one edge has both its extremities in the same subset Xi. This is why we define the following objective function f:
and seek to minimize it. We have obtained a k-coloring as soon as we have found a solution s with f(s) = 0.
In order to explain how the algorithm works, we further define the neighborhood N(s) of a solution s as being the set of the solutions s′ that we can obtain from s by moving a vertex x from a certain subset Xi (where x is adjacent to at least one vertex of Xi) to another subset Xj.
The Tabu search starts from a certain initial solution, for example obtained randomly. Every time we are in a solution s, we randomly generate a subset M of N(s), where |M| is a parameter of the algorithm.
The next current solution is the best solution in M. Since this procedure may cycle, a Tabu list T must be introduced. Since the move from a solution s to a solution s′ in N(s) consists of moving a vertex x from a set Xi to a set Xj, we add the couple (x, i) to T, with the aim of (temporarily) forbidding the return of x in the i-th subset.
When generating M, we therefore choose only solutions 
of N(s) for which 
for every couple (x, i) in T. Since the maximum size of the Tabu list is often fixed to a certain value, the oldest element of T is removed when T becomes too big.
Because this algorithm can potentially deteriorate the current solution, it is necessary to store the best solution encountered in a memory s* so as not to lose it. This solution also allows us, when generating M, to permit a solution s′ with 
, despite the couple (x, i) being present in T, on the condition that f(s″) < f(s*) (no risk of cycling in this case).
The principal stopping criterion of the Tabu search is finding a solution s with f(s) = 0, that is finding a k-coloring. We can then decrease the value of k by one unit and once again apply the Tabu search in order to attempt to obtain a better upper bound on the chromatic number. But this stopping criterion does not allow us to ensure that the algorithm stops; in particular if k < χ(G), it is not sufficient.
It is therefore necessary to introduce one or more other stopping criteria to interrupt the search. The most common are:
– a fixed number of iterations has been carried out;
– there has been no further improvement of s* for a fixed number of iterations;
– the calculation time has reached a fixed limit.
In this way we obtain the Tabu search for the k-coloring problem described below. Note that in order to accelerate the algorithm, the generation of M can be interrupted as soon as s′ with f(s′) < f(s) has been found. The Tabu search can be described as follows:
Tabu algorithm:
choose an initial solution s
s* := s; T = ∅
For the speed of the algorithm, it is important to note that the value f(s′) of a neighboring solution of s must be calculated on the basis of the known value f(s). Let us assume that the move from s = (X1,…, Xk) to s′ consists of moving a vertex x from the i-th to the j-th subset. Then:
It is therefore not even necessary, at this stage, to generate s″; x, i and j are sufficient. We can satisfy ourselves with storing these three values and updating them each time a better neighboring solution is found while generating M.
This algorithm allows us to obtain, with a few minutes of calculation time, better upper bounds than sequential algorithms. Numerical experiments are described in [FLE 96]. For random graphs with 500 vertices and more (density 0.5), it is necessary to first reduce the initial graph to a residual graph with 100 to 200 vertices before applying the algorithm presented above. This reduction is made by repeatedly finding a large stable set (with an appropriate Tabu algorithm), and then removing it from the graph (this corresponds to assigning a definitive color to this stable set) [FLE 96].
An additional advantage of the Tabu algorithm is that it is relatively easy to adapt it to various graph coloring problems, such as those that we will see later.
Another approach based on the Tabu search was used in [BLÖ 03]; it consists of considering partial k-colorings of the graph G as solutions, that is partitions of the set of the vertices of G into k disjoint subsets S1,…, Sk and one subset O (which corresponds to the non-colored vertices in this solution). The Tabu search then seeks to minimize the size of O.
From a solution s = (S1,…, Sk; O), we construct a neighboring solution 
by choosing a non-colored vertex u (u ∈ O) and giving it a color i; in doing this, we need to keep s′ as a partial k-coloring: if A(u) is the set of neighbors of the vertex u in G, we will therefore have:
The method consists of choosing from all the neighboring solutions (u ∈ O, i = 1,…, k) the one which gives a minimum |O′| as long as the assignment u → color i is not Tabu.
An important characteristic of the method from [BLÖ 03] is the introduction of a Tabu list of reactive length (that is which takes into account the evolution of the search): when a movement from s to s′ is made, that is u → color i then all the movements w → color i (for w ∈ A(u) ∩ Si) are Tabu for the following t iterations.
The length t is adjusted reactively according to |O|. If |O| oscillates a lot, t will be reduced, otherwise t will be increased: with small values of t, the method behaves like a descent method (with its disadvantages) and for large values oft, the search is wider and also more random.
In concrete terms, every b iterations we calculate the difference Δ between the maximum and the minimum of |O| during the last b iterations. We adjust t in this way:
In numerical experiments, b could vary between 500 and 50,000 and B between 5 and 50.
The algorithm receives as input a graph G and an initial solution s = (S1,…,Sk; O). Its initialization conditions are: k 1, imax 1, b 1, B 1, i = 0, t = B, and s* = s. It can be formulated as follows:
– while i imax and |O| 1 do:
- find a non-Tabu movement u → color i that minimizes |O′| (allow a Tabu movement if |O′| < |O*|);
- carry out u → color i in the solution s;
- for every w ∈ A(u) ∩ Si do: make w → color i Tabu for the following t iterations;
- if i ≡ 0 (mod b) then:
Δ = max |O| − min |O| on the last b iterations;
if Δ < 2 then t = t + B; otherwise t = t −1;
i = i + 1;
- if |O| < |O*| then s* = s,i = 0.
This algorithm has been tested on graphs from the DIMACS database, which are generally used for comparing coloring algorithms. It provided excellent results in reasonable times; these are given in [BLÖ 03]. Note that it was possible to color the graph flat300_28_0 in 28 colors, a performance that, to our knowledge, no other heuristic has been able to equal.
10.6. Perfect graphs
While coloring problems are generally hard for arbitrary graphs, the class of perfect graphs has the particularity of containing graphs for which the chromatic number can be calculated in polynomial time [GRÖ 88]. In the most general cases of perfect graphs, the known polynomial algorithms are general linear programming algorithms; we will restrict ourselves here to considering classes of graphs for which combinatorial algorithms are known.
A simple graph G = (X, E) is perfect if for every induced subgraph H of G we have χ(H) = ω(H), that is the chromatic number of H is equal to the maximum cardinality ω(H) of a clique of H.
Since the complement graph 
of G (that is the graph obtained from G by eliminating all the edges of G and by adding all those that were missing in G) is perfect if and only if G is perfect (see [BER 83]), we deduce that a graph G is perfect if it satisfies α(H) = θ(H) for every induced subgraph H of G (that is the stability number α(H) of H is equal to the minimum number θ(H) of cliques of H covering the set of the vertices of H).
The strong conjecture of perfect graphs formulated by Claude Berge 40 years ago says that G is perfect if and only if neither G nor its complement 
contain odd cycles without a chord of length at least five. This conjecture was proved in 2002 by Chudnovsky, Robertson, Seymour and Thomas [CHU 02].
We refer the interested reader to works that deal more specifically with perfect graphs [BER 83, BER 84, GOL 84, GRÖ 88] and we limit ourselves here to describing a few subclasses of perfect graphs, highlighting their algorithmic and chromatic properties.
Comparability graphs are simple graphs G = (X, E) such that we can give an orientation to each edge in such a way as to obtain the directed graph associated with a transitive and antisymmetric relation. An example of a comparability graph, and of one that is not, is given in Figure 10.4.
Figure 10.4. A comparability graph and a graph that is not a comparability graph
As an example, the bipartite graphs G = (X, Y, E) are comparability graphs: we see this when orienting each edge [x, y] with x ∈ X, y ∈ Y from x to y.
More generally, comparability graphs are graphs G = (X, E) in which we can find an orientation that contains neither circuits nor the configuration (a, b), (b, c), represented in Figure 10.5, with a < b < c and [a, c] ∉ E.
Figure 10.5. Forbidden configuration in a transitive orientation
For these graphs the coloring algorithm is particularly simple once the orientation is defined: since this concerns a graph without any circuits, we can sort its vertices x in non-decreasing order of their rank r(x) (the rank r(x) of a vertex x is the maximum number of vertices encountered on a path that ends at the vertex x).
We can then color the vertices with a common sequential algorithm, giving the smallest possible color to each vertex (in fact, each vertex x will be given the color r(x)). It is easy to verify that χ(G) = ω(G), since the number of colors used in this coloring is equal to the number of vertices encountered on a longest path and this path induces a clique in the graph by transitivity of the orientation. To find out whether a graph G is a comparability graph, we use (polynomial) algorithms by edge orientation through propagation (avoiding the configuration in Figure 10.5) (see [GOL 84]).
Chordal graphs are such that every cycle with a length greater than or equal to four has a chord (that is an edge that joins two vertices that are not consecutive in the cycle).
These graphs are characterized by property 10.4.
PROPERTY 10.4.– G is chordal if and only if every induced subgraph has a simplicial vertex (that is such that all its neighbors form a clique).
By using this property, we can construct an order y1, y2,…, yn of the n vertices of a chordal graph G = (X, E):
let G(i) be the induced subgraph of G generated by X – {yn, yn−1,…, yi+1};
we have G(n) = G:
for i = n to 1 do:
choose for yi a simplicial vertex x from G(i).
If we next direct all the edges [yi,yj] from yi to yj if i < j, then we obtain an orientation that contains neither any circuits nor the configuration (a, c), (b, c) from Figure 10.6 (with a < b < c and [a, b] ∉ E).
Figure 10.6. Forbidden configuration in the orientation associated with a chordal graph
A coloring of the graph G is obtained using a sequential algorithm (based on the order y1,…, yn); it is easy to see that this coloring uses a minimum number of colors: if a vertex u has been given the largest color k then it is because it has at least one vertex v of color i < k which precedes it in the order (for every i < k). Since the configuration in Figure 10.6 is forbidden, all the predecessors of u are pairwise joined by edges and they therefore form a clique (with k vertices if we include the vertex u itself). In this way we have obtained a coloring where the number k of colors used is equal to the size k of a clique of G. The number k of colors is therefore minimum and the size k of the clique is maximum.
These two well-known classes of perfect graphs are included in the family of perfectly orderable [CHV 84] graphs: this consists of graphs G = (X, E) for which we can find an order < of the vertices (and therefore an orientation without any circuits for the set E of its edges) in such a way that the configuration in Figure 10.7 is forbidden:
Figure 10.7. Forbidden configuration in the orientation associated with a perfectly orderable graph
In other words, the directed graph cannot contain any induced chains on four vertices a, b, c, d (see Figure 10.7), where a < b and c < d.
The orientation defined for comparability graphs does not contain the obstruction in Figure 10.7 (since the obstruction in Figure 10.5 is contained in the obstruction in Figure 10.7); comparability graphs are therefore perfectly orderable graphs. The graph in Figure 10.4a is perfectly orderable, but is not a comparability graph.
Similarly, the orientation defined for chordal graphs cannot contain the obstruction in Figure 10.7 (since the obstruction in Figure 10.6 is contained in that in Figure 10.7), which shows that chordal graphs are perfectly orderable. The graph consisting of the edges [a, b], [b, c], [c, d], and [a, d] is perfectly orderable but is not chordal.
For perfectly orderable graphs, any order of vertices such that the associated orientation does not include the obstruction in Figure 10.7 can be used in the sequential coloring algorithm. We can show that we still obtain a coloring using k colors if k is the maximum size of a clique of G [CHV 84].
The class of perfectly orderable graphs is interesting with regard to coloring because of the simplicity of the exact coloring algorithm. Unfortunately, it is hard to find out whether a graph is perfectly orderable; the problem is NP-complete [MID 90]. We must therefore confine ourselves to recognizing subclasses of perfectly orderable graphs in polynomial time. Other subclasses of perfect graphs are interesting because of their field of application. Among these are interval graphs: we say that a simple graph G = (X, E) is an interval graph if there exists a family {common_X} = {x1,…, xn} of intervals on the real line such that by associating a vertex xi of G with each interval xi of {common_X}, we have [xi, xj] ∈ E if and only if the corresponding intervals have a non-empty intersection.
PROPERTY 10.5.– [BER 83] A graph G is an interval graph if and only if G is chordal and its complement 
is a comparability graph.
Thus, since such a graph is chordal, we can construct an order of the vertices y1,…, yn in such a way as to be able to use the classical sequential coloring algorithm. Here, if we denote by xi = [ai, bi] the intervals of {common_X}, the order is obtained by sorting the intervals in the order of the non-increasing extremities (right-hand limit) bi and we color them in this order with the smallest color possible.
As an example, interval graphs can be used to model memory usage problems in programming. Let us assume that the intervals of time between the first and last use of each of the variables in the execution of a program is known. Knowing that in the same memory (or the same register), we can store variables whose life intervals are disjoint, minimizing the number of memories (or registers) necessary is the same as finding an optimal coloring (that is with a minimum number of colors) in the interval graph associated with the variables. Intervals of color i will be associated with the variables that can be stored in the memory i.
In reality, this type of problem becomes very important in programs that contain loops; we then need to use circular interval graphs that are associated with intervals situated on a circle instead of a straight line. These graphs are no longer perfect and coloring them is generally a hard problem (see [GOL 84]).
Applications and developments for the loops in computer program problems are mentioned in [WER 99b]. Circular interval graphs are also a tool that allows us to study the operation of traffic lights at crossroads (see Chapter 3 in [ROB 76]): optimizing the “green” phases for the various traffic flows is done by solving one (or several) linear programming problem(s) whose structure is based on constructing a circular interval graph.
Lastly, a very special class of perfect graphs deserves a mention: this is permutation graphs [GOL 84].
Let P = (p1, p2,…, pn) be a permutation of the integers 1, 2,…, n. We associate a graph G(P) with it by adding the vertices 1, 2,…, n and by joining i and j with an edge if i < j and if j precedes i in P. This means that if p−1(ℓ) refers to the position occupied by ℓ in the permutation (p−1(ℓ) = k, if pk = ℓ) then i and j are joined if i < j and p−1(j) < p−1(i). Figure 10.8 shows a permutation P and the associated graph G(P).
Figure 10.8. A permutation P and the associated graph G(P)
A graph G = (X, E) is called a permutation graph if there exists a permutation P of 1,2,…, |X| such that (by renaming the vertices 1, 2,…, n) G is the graph G(P) associated with P.
PROPERTY 10.6.– [PNU 71]. A simple graph G is a permutation graph if and only if G and 
are comparability graphs.
This property is the basis for algorithms for permutation graph recognition by construction of transitive orientations; see [GOL 84] for examples.
If P is a permutation, the decreasing subsequences of P correspond to the cliques of G(P) and the increasing subseries with the stable sets of G(P). Since permutation graphs are perfect, there is equality between the chromatic number χ(G(P)), the minimum number of increasing subsequences that cover the set {1, 2,…, n}, and the maximum length of a decreasing subsequence.
10.7. Chromatic scheduling
When formulated in terms of graph coloring, the scheduling problem given at the beginning of this chapter belongs to the domain of chromatic scheduling. This concerns the set of scheduling or timetabling problems that may be modeled (and solved) with the help of coloring concepts and their extensions. If chromatic scheduling was restricted to problems that are solvable using classical coloring concepts, the domain would be far too limited and many scheduling problems would be excluded from it.
This is the reason why we go on to present a few extensions and variations of the coloring concepts that have been introduced with precisely the objective of gaining an understanding of the wider field of timetabling problems.
Let us consider a scheduling problem characterized by a set X of indivisible tasks x1,…, xn of the same length (let us say one day). To this we add some precedence constraints on the execution of the tasks, that is a set U of ordered couples (xi, xj) of tasks that signifies that for each couple (xi, xj) the task xi must precede the task xj (that is xi must be assigned to a day c(i) such that c(i) < c(j) if c(j) is the day on which xj is executed). Next, as before, we have a collection E of non-ordered couples [xi, xj] showing that the tasks xi and xj cannot be executed simultaneously (disjunction constraints).
We must now establish an assignment of the tasks to the days that satisfies the constraints defined by the sets U and E. Whether a schedule in k days exists or finding a schedule of minimum length are the questions that may be asked.
We associate a mixed graph with this scheduling problem, that is a graph which has both (non-directed) edges and arcs (directed by definition): each task xi corresponds to a vertex of G; each precedence constraint (xi, xj) is associated with an arc (xi, xj) and, as before, each disjunction constraint is represented by an edge [xi, xj]. Such a graph will be denoted by GM = (X, U, E).
Now, we can define a k-coloring of a mixed graph GM = (X, U, E) as assigning to each vertex i a color c(i) chosen from the (ordered) set {1,…, k} in such a way that for each arc (xi, xj) of U, we have c(j) > c(i), and for each edge [xi, xj] of E, we have c(i) ≠ c(j). In the same way, we refer to coloring if the value of k is not stated.
Note that the notion of k-coloring a mixed graph naturally generalizes the notion of k-coloring a simple graph.
It must be emphasized that, contrary to the classical case, a k-coloring for any value of k may not exist. Indeed, we have the following condition.
PROPERTY 10.7.– A graph GM = (X, U, E) has a coloring if and only if the partial directed graph G = (X, U) does not contain any circuits.
The justification relies on the fact that we can always direct the edges of E in such a way as to obtain, with the arcs of U, a directed graph that does not contain any circuits.
Let us further note that a disjunction constraint (represented by an edge [xi, xj]) can be interpreted by saying that we must have either c(i) < c(j) (arc (xi, xj) in the graph) or c(j) < c(i) (arc (xj, xi) in the graph). This implies c(j) ≠ c(j).
We will denote by χM(GM) the smallest k such that GM = (X, U, E) has a k-coloring; we will call this the mixed chromatic number (of a mixed graph GM).
It is clear that χM(GM) is always greater than or equal to the maximum number of vertices that we encounter on a path (made up by definition of arcs (directed)) in G = (X, U); by denoting this number by ℓ(U), we have χM(GM = (X, U, E)) ℓ(U).
Various bounds on χM(GM) are given in [HAN 97]. In particular, we show that for a bipartite graph GM = (X, U, E), we have ℓ(U) χM(GM) ℓ(U) + 1. For a mixed tree TM = (X, U, E), it is possible to find in polynomial time if χ(TM) = ℓ(U), however, for a bipartite mixed graph, the problem is NP-complete (this is a consequence of results given in [BOD 94]). More precisely, the 3SET problem below is NP-complete: given a bipartite graph G and three vertices v1, v2, v3 of G, does a 3-coloring of G where the vertex vi has the color i (i = 1, 2, 3) exist? We show that we can reduce 3SET to 3-coloring a mixed bipartite graph by associating a path (v1,a)(a,b) with v1, a path (c,v2)(v2,d) with v2, and a path (e,f)(f,v3) with v3, where a, b, c, d, e, f are new vertices. So 3SET has a solution if and only if the graph 
constructed in this way satisfies 
.
Some experiments with a heuristic algorithm are recounted in [HAN 97]; but there are still many directions to explore with the aim of developing effective algorithms for problems of large size.
10.8. Interval coloring
Up to this point, the scheduling problems that could be modeled using coloring concepts and their extensions have been restricted to considering sets of tasks with the same length of execution. While this restriction is acceptable, particularly in the context of school timetable problems (where each task represents a lecture that lasts one hour), it must be admitted that in the majority of applications, the tasks xi that we handle have lengths di which can be different from each other but which we assume to be integers (number of days or of hours, for example). We will continue to assume that the tasks are indivisible here, that is that a task must always be executed without interruption.
At this stage we consider mixed graphs GM = (X, U, E) where a positive integer di is associated with each vertex xi that represents the length of the task xi that corresponds with this vertex. Such a graph will thus be expressed by 
where D is the assignment of integers di to the vertices.
The precedence constraints of U therefore mean that if we have an arc (xi, xj), the task xi (which starts on day c(i) and finishes at the end of day c(i) + di − 1) is finished before day c(j), when task xj starts, that is we must have:
With regard to the disjunction constraints, each edge [xi, xj] of E imposes that that we have one of the two possibilities:
An interval k-coloring of a mixed graph 
is an assignment of di consecutive integers c(i), c(i) + 1,…, c(i) + di − 1 to each vertex xi in such a way that:
a) c(j) c(i) + di for every arc (xi, xj) of U;
b) c(i) + di c(j) or c(j) + dj c(i) for every edge [xi, xj] of E.
The interval chromatic number 
of 
is the smallest integer k such that 
has an interval k-coloring. Since this is an extension of the classical coloring problem, it is clear that this problem is generally hard.
With the aim of giving bounds on 
in a relatively simple form, we will now assume that we do not have any precedence constraints (U = ∅). We will denote by NG(xi) the set of the neighbors of the vertex xi in the graph G, and dG(xi) will be the degree of the vertex xi in the graph G (that is the number of edges incident to xi).
PROPERTY 10.8.– [WER 88] For every graph 
of vertices x1,…, xn:
With methods that generalize the methods used for classical graph colorings very directly, we can obtain a second form.
PROPERTY 10.9.– [WER 88]
Here 
means that H is an induced subgraph of 
, and xi ∈ H signifies that xi is a vertex of the graph H.
A sequential coloring algorithm can be defined to color a mixed graph in the above sense in such a way that the number of colors used does not exceed the value given in property 10.9. This will consist of constructing, starting with the last position, an order y1,…, yn of the n vertices x1,…, xn of 
. This algorithm is as follows:
– 
; i = 1;
– while H still contains vertices do:
- choose a vertex xp such that:
is minimum;
- put xp in the last position still free (i.e. set yn−i+1 := xp);
- eliminate xp from H (that is to say state H := H − xp);
- i := i + 1.
If we then color the vertices in the order y1, y2,…, yn, each time using the smallest consecutive colors possible, then we can verify that we obtain an interval coloring that satisfies the bound in property 10.9.
Lastly, it is a good idea to note that if the scheduling problem formulated at the start of this section has, on the contrary, only precedence constraints (and no disjunction constraints), then it enters exactly into the scope of classical scheduling problems where critical path methods allow us to find (by finding a path of maximum length in an appropriate graph) a schedule of minimum duration in polynomial time.
10.9. T-colorings
While applications of coloring methods to timetabling problems are the best known and the oldest, more recently the same techniques have been used in the telecommunications domain, and in particular for questions regarding assignment of frequencies to transmitters. We propose further generalizing the notions of coloring that we have studied up until now in order to be able, using appropriate concepts, to formulate frequency assignment problems such as those which arise in situations where we must avoid unwanted interference.
In the interval coloring problem, we can reuse the two types of constraints (precedence and disjunction) by seeking to reformulate them:
a) Precedence constraint represented by an arc (xi, xj). This implies c(j) c(i)+ di or even c(j) − c(i) di. We can associate a set 
of allowed values for the difference c(j) − c(i) with the arc (xi, xj). Here, therefore, we will have 
. It is customary to consider the complement Tij of 
and therefore we will have Tij = {…, di − 2, di − 1} with the requirement c(j) − c(i) ∉ Tij.
b) Disjunction constraint represented by an edge [xi, xj]. By definition, we must have:
- either c(j) c(i) + di, that is c(j) − c(i) di;
- or c(i) c(j) + dj, that is c(j) − c(i) −dj.
In other words, the value of c(j) − c(i) must not be included between −dj + 1 and di − 1. Contrary to previous practice, we can associate a directed arc (xi, xj) arbitrarily directed from xi to xj (rather than an edge [xi, xj], which is non-directed by definition) with a disjunction constraint concerning the couple of tasks xi, xj and define Tij = {−dj + 1, −dj + 2,…, 0,…, di − 2, di − 1}. We should then have c(j) − c(i) ∉ Tij as in the precedence constraint case. If we chose the opposite orientation, that is (xj, xi), we would have defined Tji = {−di + 1,…, 0,…, dj − 1}; note that Tij ≠ Tji if di ≠ dj.
In this way, we obtain a similar formulation for the two types of constraints (in one case the set Tij is finite, in the other it is not). The set of the possible values for c(j) − c(i) is an interval for the precedence constraints, and it is a collection of two disjoint intervals for the disjunction constraints.
In this way we can define the notion of T-coloring for a graph GD, which will now be a directed graph GD = (X,U,∅, D, T), where ∅ is the empty set which expresses the absence of edges in the graph and where T represents the parameter for each arc (xi, xj) of U from a set Tij of forbidden values for c(j) − c(i).
A T-coloring (in k colors) of a directed graph GD = (X,U, ∅, D, T) is an assignment of di consecutive integers c(i), c(i)+1,…, c(i)+di −1 (chosen from {1,…, k}) to each vertex xi, such that for every arc (xi, xj) we have c(j) − c(i) ∉ Tij.
By analogy with what was done above, we can define 
, the T -chromatic number of GD, as the smallest k for which a T-coloring of GD in k colors exists. Before giving upper bounds on 
, we would like to return to the case of classical vertex colorings. To return to these, we must set di = 1 for each vertex xi (in effect a vertex is given one color) and Tij = {0} for every arc (xi, xj) of GD, that is c(j) − c(i) ∉ {0}, or even c(j) ≠ c(i), for every arc (xi, xj).
At this stage, we can consider that a classical coloring problem such as was for-mulated at the start of this chapter can, in fact, be associated with a directed graph GD = G = (X,U) with for each arc (xi, xj) a set Tij = {0} (by choosing the op-posite arc (xj, xi) instead of the arc (xi, xj), we would also have Tji = {0}, which shows that the orientation is arbitrary for classical colorings).
In frequency assignment problems, the sets Tij of values forbidden for c(j) − c(i) are symmetrical with regard to 0 (−r ∈ Tij if and only if r ∈ Tij). We therefore have |c(j) − c(i)| ∉ Tij, which again allows us to consider the problem as being stated in an undirected graph.
It must be said again that T-colorings do not always exist in directed graphs GD: let us consider, for example, the arcs (xi, xj) that represent precedence constraints (Tij is then a set in the form {…, di − 2, di − 1}); it is necessary that the partial directed graph generated by the arcs associated with precedence constraints does not contain any circuits. It is relatively easy to be persuaded that this condition is also sufficient for a T-coloring to exist.
In order to be able to give an upper bound on the T-chromatic number, let us, for each arc (i,j), introduce the number gij = |Tij| − di + 1, and let us formulate the hypothesis that each Tij is a set of consecutive integers (which includes the value 0). When we talk about an arc (xi, xj), we are aware that its orientation is arbitrary and that it could be inverted by further replacing Tij with Tji.
When we consider the set NH(xi) of the vertices xj that are adjacent to a vertex xi in an induced subgraph H of G, we may therefore assume that all the arcs between xi and xj are directed from xi to the other vertex, say xj. By following [WER 94], we then have the following bound for the T-chromatic number.
PROPERTY 10.10.– [WER 94] For a graph GD = (X, U, ∅, D, T) with sets Tij which are sets of consecutive integers that include the value 0:
It is interesting to note that, even if this bound seems to require that we consider all the induced subgraphs H of GD, it can be calculated in polynomial time [WER 94], and that a sequential coloring algorithm may be used to obtain a T-coloring that satisfies property 10.10.
Let us define the function f(z, H), where z is a vertex of the graph H, by:
We will define an order y1, y2,…, yn of the |X| = n vertices x1,…, xn of GD (starting with the end). Let us denote by G(i) the induced subgraph of GD = (X, U, ∅, D, T) generated by the set X − {yi+1,…, yn}; we have G(n) = GD:
for i = n to 1 do:
let yi be a vertex of G(i) such that 
By then coloring the vertices in the order y1,…, yn (using the smallest possible color each time), we obtain a T-coloring that satisfies property 10.10.
Numerical experiments with various sequential algorithms are described in the article [WER 94]; these methods are direct adaptations of known algorithms for classical graph colorings.
In applications to frequency assignments, the idea is generally to assign to each transmitter site xi (represented by a vertex xi of the associated graph) a transmission frequency in such a way as to avoid interferences with neighboring transmitters (represented by vertices xj adjacent to the vertex xi). These interferences occur if the frequencies c(i) and c(j), assigned to the neighboring transmitters xi and xj, respectively, satisfy a relationship:
Tij is therefore a set of forbidden values for the difference between the frequencies of the neighboring transmitters xi and xj (as mentioned above, in general we have Tij = Tji and the problem can be considered as non-directed).
In these types of applications, we have |Tij| < ∞. The objective can be to minimize either the number of different frequencies used in the network modeled by the graph GD, or the difference between the largest and the smallest frequencies used (bandwidth). The algorithms mentioned above are adapted for the first objective. Appropriate methods could be developed to attempt to minimize the bandwidth.
10.10. List colorings
The disjunctive constraints and precedence constraints that appear in chromatic scheduling problems may be considered as similar in the sense that they are local constraints which concern specific subsets of vertices (in this case couples of vertices). Other local constraints often appear in timetabling problems, each one concerning only one vertex. These constraints restrict the colors that can be assigned to each vertex.
Here we consider a graph G = (X, E) without any precedence constraints, where with each vertex x we associate a set φ(x) ⊆ {1,…, k} of eligible colors for this vertex (where k is the number of colors available). Such a graph will be denoted by 
. The list k-coloring problem consists of establishing whether there exists a k-coloring c of G such that each vertex x is given an eligible color c(x) ∈ φ(x). We talk of simple list coloring if the number of colors k is not specified. This problem can easily be extended to mixed graphs, but we will not tackle this extension here.
In school timetabling problems, this type of constraint allows us, for example, to take into account the unavailability of teachers at certain times. If a teacher is not available for a time i, this can be modeled by removing the color i from the set of eligible colors for this teacher’s lectures. For task scheduling problems, we can in this way take into account that it is forbidden to execute certain tasks on a given day.
Since we can assume that k is bounded polynomially by the number of vertices n (the vertices x for which |φ(x)| n can be removed from the graph without affecting the existence of the k-coloring sought), the list k-coloring problem has a complexity that is at least as large as the k-coloring problem. In fact, this problem is even NP-complete for planar bipartite graphs with k = 3.
There is also a link between the list k-coloring problem and an edge orientation problem, but it is less strong than that of property 10.1.
PROPERTY 10.11.– [TUZ 97] If we can direct each edge of a graph 
in such a way as to obtain a directed graph without any circuits of odd length and with, for every vertex x, at most |φ(x)| − 1 arcs leaving from x, then 
has a list-coloring.
With an additional condition, this result can be extended by allowing the presence of circuits of odd length, but the existence of such an orientation remains simply a sufficent (and not necessary) condition [ALO 92].
Another sufficient condition is given by what we call the Hall conditions, property 10.12.
PROPERTY 10.12.– [WER 99a] Let there be a graph 
. For every A ⊆ X and every partition of X into cliques K1,…,Kp:
is a necessary condition for the existence of a list-coloring (where Ai = A ∩ Ki).
These conditions are sufficient in the case where the graph is a collection of disjoint cliques, and we can restrict ourselves to the partition into cliques which consists of taking the connected components of the graph. The problem can then be solved using network flow techniques (polynomial solution method).
If the size of the sets of eligible colors is sufficiently large, the existence of a list-coloring is guaranteed. Indeed, if each vertex has more colors allowed than neighbors, it will always be possible to color it. Thus if |φ(x)| Δ(G) + 1 for every vertex x, there necessarily exists a list k-coloring of G.
The smallest integer t such that there exists a list-coloring of G for every assignment of eligible colors φ that satisfies |φ(x)| t is represented by χℓ(G), and can be called the list-chromatic number of G. We have just seen that χℓ(G) Δ(G) + 1, and it is easy to be persuaded that χ(G) χℓ(G). In the case of planar graphs, it has been shown that χℓ(G) 5, and χℓ(G) 3 if they are also bipartite.
As outlined in the first section, the list k-coloring of a graph Gφ = (X, E, φ) can be reduced to the question of whether there exists a stable set of |X| vertices in an auxiliary graph 
. This latter is constructed as for the graph 
presented in section 10.1, with the slight difference that we remove the copy ai of a vertex a when i is not an eligible color for a (that is I ∉ φ(a)). In this way, we are guaranteed that the i-th copy of the vertex a can never be in a stable set of 
, and therefore that we will not assign the color i to it.
It is therefore possible, thanks to this transformation, to use existing solution methods for the maximum stable set problem to tackle the list k-coloring problem. We can also propose an adaptation of the Tabu search for this problem. While for the common coloring problem a movement consists of choosing a vertex x that has a neighbor of the same color and modifying its color, here it is sufficient to restrict the choice of the new color to the allowed colors φ(x). Another adaptation would consist of allowing the partitions in which a vertex has a forbidden color, but penalizing this state. For this, we can add a given constant to the value of the objective function for each vertex that has a forbidden color.
There are no reports in the literature of tests of these adaptations, partly because it is also possible to transform a list k-coloring problem on a graph Gφ = (X, E, φ) into a common k-coloring problem on a graph G′ = (X ∪X′, E ∪E′) obtained in the following way. Starting from the graph G = (X, E), a clique 
of size k is added. Each vertex x of G is then joined to all the vertices Gφ that represent colors i not allowed for x (that is that do not belong to the set φ(x)). There is a biunivocal correspondence between the list k-colorings of Gφ and the k-colorings of G′. Indeed, a list k-coloring of Gφ can be extended to a k-coloring of G′ simply by coloring the vertex 
with the color i. Reciprocally, in the case of a k-coloring of G′, we can assume that the vertex 
has been given the color i (even if it means renumbering the colors); the edge [x, 
] then allows us to ensure that the vertex x has not been given the forbidden color i. This transformation slightly increases the size of the graph to be colored, but then allows us to apply the algorithms developed for the common coloring problem as they are.
Let us now examine a special case: precoloring extensions. In the precoloring extension problem, a subset of vertices P ⊂ X of the graph G = (X, E) is precolored with:
where k is the number of colors. The question is to establish whether G allows a k-coloring that extends 
, that is whether it is possible to assign a color from the set {1,…, k} to the vertices of X\P, taking into account colors that the vertices in P already have. In the special case where P = ∅, we come back to k-coloring.
Study of this problem was spurred on by the observation that, on interval graphs, it allows us to model an airplane management problem [BIR 92]. This consists of assigning flights to a certain number of airplanes according to a timetable, with the condition that the service schedule (fixed for each airplane) is not modified.
The restricted-coloring (or list-coloring) problem was introduced later (and for other reasons), but is a generalization of the precoloring extension problem. In effect, it is sufficient to reformulate the latter by associating a list of eligible colors with every vertex:
Like the list-coloring problem, the coloring extension problem is NP-complete for planar bipartite graphs with k = 3. If we represent the set of the vertices precolored with the color i by Pi, we can assume, without loss of generality, that |P1| |P2| … |Pk|. The problem is polynomial for perfect graphs if P3 = ∅ and |P2| 1, and for interval graphs when |P1| = 1. Other results on the extensions of coloring and list-coloring can be found in [TUZ 97].
10.11. Coloring with cardinality constraints
Sometimes local constraints, which only concern a few vertices (two or one in the problems presented above), are not sufficient for modeling other forms of constraints, which are nonetheless very natural. It may be necessary to introduce constraints of a global nature that concern the graph in its entirety. Such an example is given by cardinality constraints, which restrict the number of vertices of each color. We consider a graph G = (X, E) to be colored with a number k of colors, with the additional condition that it is forbidden to have more than hi vertices of the color i, where the hi are given bounds. The k-coloring with cardinality constraints problem consists of establishing whether such a k-coloring exists. Again, the problem could easily be extended to mixed graphs.
This type of constraint is used, for example, in modeling scheduling problems to take into account the availability of certain resources, such as personnel or machines. Indeed, since in this type of problem a color corresponds to a day, the cardinality constraint hi can be fixed to the number of machines available during the day i. In this way, it is possible to ensure that each task will have a machine available for it. Similarly, in school timetabling problems, these constraints allow us to take into account the number of classrooms available each hour.
By putting hi equal to the number of vertices of the graph under consideration, we realize that the k-coloring problem is a special case of this problem. It is therefore hard. In fact, it is NP-complete for interval graphs (even if all the hi are equal to four) and bipartite graphs. The only known classes for which the problem can be solved in polynomial time are disjoint cliques and complements of graphs without triangles. Necessary conditions are given by property 10.13.
PROPERTY 10.13.– [WER 99a] Let there be a graph G = (X, E) with cardinality constraints hi, i = 1,…, k. For every A ⊆ X, every C* ⊆ {1,…, k} and every partition of X into cliques K1,…, Kp:
is a necessary condition for the existence of a k-coloring with cardinality constraints (where κA is the number of cliques Kj that intersect A).
As in the case of property 10.12, these conditions are sufficient for graphs that are disjoint cliques.
A special case of the k-coloring with cardinality constraints problem, which is more extensively reported in the literature, is the case where all the bounds hi are equal to a certain value h. We then define the bounded chromatic number χh(G) as being the smallest integer k for which there is a k-coloring of G with at most h vertices of each color.
It is easy to see that χh(G) = χ(G) when h α(G). Indeed, in every k-coloring of G, each set of vertices that have the same color forms a stable set, which is necessarily of size at most α(G) (by definition). Similarly, we clearly know that χ1(G) is equal to the number n of vertices in G. A final value that we can obtain in polynomial time for any G is χ2(G). Indeed, if E′ is a maximum matching in the complement graph 
(a matching is a set of pairwise non-adjacent edges), we have χ2(G) = n − |E″|. Now, a maximum matching can be found in polynomial time [LAW 76].
For the other values of h, it is possible to bound the value of χh(G) by:
where n is the number of vertices in G [HAN 93]. The bound 
comes directly from the fact that we seek to cover n vertices with sets of a size of at most h. In the case of claw-free graphs (that is graphs that do not contain the structure in Figure 10.9), the lower bound is even equal to χh(G).
The upper bound depends on the chromatic number χ(G), which itself is generally hard to establish. This is why it may be useful to have another upper bound which is
Figure 10.9. The claw
simpler to calculate. If we put aside cliques (for which χh(G) = Δ(G) + 1) and odd cycles when 
(for which χh(G) = 3), we have:
For bipartite graphs, it is even possible to give an upper bound that differs from the lower bound by at most 1. Let us consider a bipartite graph that has as its set of vertices X = X1 ∪ X2 and edges only between X1 and X2. The absence of edges that join two vertices of X1 allows us to color X1 with at most 
colors. The same reasoning can be applied to X2, and therefore:
But, as already mentioned, the problem of establishing the right value is NP-complete. In the special case of trees, the problem becomes polynomial.
As for the other problems, the most natural way to solve an instance of this problem consists of using an adaptation of the known methods for the k-coloring problem. In the case of the Tabu search, we can keep the same method of solution (a partition of the set of vertices into k subsets) and add to the objective function a value proportional to:
for every color i that violates its cardinality constraint. In this case, a movement would consist of modifying the color of either a vertex that has a neighbor of the same color, or a vertex that has a color that is used too frequently (with regard to the cardinality constraint).
Let us now examine a special case: list-colorings with cardinality constraints. We have seen in the previous sections that cardinality constraints, as well as sets of eligible colors for the vertices, appear naturally, for example in school timetabling problems. In the case where the graph G under consideration is a simple chain, the list-coloring problem with cardinality constraints also corresponds to the following situation.
Tasks of number n, each one having an execution length of one period, are placed on a line at regular intervals. A set φ(v) of periods at which v can be executed is given for each task v. These tasks are handled by robots of which hi are available during the period i. Because of the space needed by these robots, two tasks that are located on adjacent places on the line (that correspond with two adjacent vertices in G) cannot be executed at the same time. Establishing whether there exists an admissible timetable with k periods to carry out these tasks is equivalent to the problem of whether a list k-coloring of 
with cardinality constraints hi exists.
Unfortunately, this problem is NP-complete, even if each task has at most two periods in which it can be executed. The only class of graphs for which a polynomial algorithm is known is that of disjoint cliques. In this case, a flow algorithm allows us to solve the problem [WER 99a].
Properties 10.12 and 10.13 presented in the previous sections are in fact special cases of property 10.14.
PROPERTY 10.14.– [WER 99a] Let there be a graph Gφ = (X, E, φ) with cardinality constraints hi, i = 1,…, k. For every A ⊆ X, every C* ⊆ {1,…, k}, and every partition of X into cliques K1,…, Kp:
is a necessary condition for the existence of a list k-coloring with cardinality constraints (where Ai = A ∩ Ki).
These conditions are sufficient when G = (X, E) is a collection of disjoint cliques, and these graphs are the only ones for which these conditions are sufficient whatever the choice of φ and the hi.
10.12. Other extensions
Despite the complexity of the formulae that give bounds on the T-chromatic number, the models of graphs described up to now are not yet capable of encompassing all the types of constraints that we can encounter in real problems.
In the models described above (except in the case of cardinality constraints), we restricted ourselves to considering constraints that concern isolated tasks or couples of tasks; whether this concerned precedence or disjunction, two tasks participated in formulating the constraint. The forbidden colors constraints were linked to one task.
We can nonetheless imagine a more general description of disjunction constraints, which would be formulated by giving a set R of tasks and an integer r with the requirement that from the tasks in R there are at most r that can be executed simultaneously. (In the case of disjunction constraints, we had |R| = 2 and r = 1 for each constraint.) This type of constraint arises most notably when a resource (known as “renewable” by specialists in scheduling because it is used by tasks as a machine would be rather, than definitively consumed, as a fuel would be) is available in a quantity r; the tasks of R each use one unit of this resource during their execution.
The model that we associate with such a problem is then a hypergraph (constructed as before over vertices associated with the tasks) whose sets R (|R| 2) associated with the constraints are the edges.
These models are more complex than those based on graphs and, apart from very special cases, do not give rise to exact algorithms that are polynomial (see [BER 87]). Heuristic methods have to be developed for these more general cases; deriving bounds on the chromatic number of these hypergraphs can, in certain cases, be based on the techniques used for graphs by generalizing them.
10.13. Edge coloring
In very specific cases, we can formulate a timetabling problem in terms of edge coloring. Given a multigraph G = (X, E) (it can have multiple edges, but no loops), a k-coloring of the edges of G is an assignment of a color c(e) to each edge e, chosen from the set {1,…, k} in such a way that two adjacent edges are always of different colors. The smallest number k of colors such that G has a k-coloring of edges is the chromatic index of G, sometimes denoted by χ′(G). Clearly, we have Δ(G) χ′(G); Vizing [VIZ 64] showed that for simple graphs we also have χ′(G) Δ(G) + 1. Establishing whether χ′(G) = Δ(G) is an NP-complete problem [HOL 81], even for r-regular graphs (that is graphs for which all the vertices have a fixed degree r) [GAL 83].
The edge coloring model is generally used in the most simple cases of the school timetabling problem where we have a set M of teachers mi, a set C of classes (groups of pupils) cj, and a collection E of lectures (each one lasting one hour) characterized by the teacher mi who gives it and the class cj that attends it. To associate a graph with the problem of constructing a timetable in k hours, we add one vertex for each mi, one vertex for each cj, and each lecture implies that mi and cj is represented by an edge [mi, cj]; the obtained graph G = (M, C, E) is bipartite. It is known that χ′(G) = Δ(G) for bipartite multigraphs (see [BER 83]). We can easily verify that there is a correspondence between timetables in k hours and k-colorings of edges of G, since a teacher cannot give two lectures simultaneously and a class cannot attend more than one lecture at a time. We can find some extensions and variations of this model in [WER 97].
Edge coloring models are in fact special cases of the (vertex) colorings defined previously. It is sufficient to note that we can always transform the edge coloring problem of a multigraph G with k colors into a k-coloring problem of the vertices of a simple graph L(G) associated with G (called a line graph of G). L(G) is obtained by introducing a vertex 
for each edge e of G and joining in L(G) the vertices 
and 
if they correspond to adjacent edges e, f of G. We then notice that there is a correspondence between k-colorings of edges of G and k-colorings (of vertices) of L(G). Figure 10.10 gives an example of a timetabling problem with the transformation described above. In Figure 10.10a, the bipartite multigraph G associated with a school timetabling problem (two teachers, two classes, five lectures) is shown. In Figure 10.10b the line graph L(G) of the multigraph G from Figure 10.10a is shown.
Figure 10.10. Transforming an edge coloring problem into a (vertex) coloring problem
However, we cannot generally transform a k-coloring of vertices problem into a k-coloring of edges problem.
In the case of bipartite multigraphs, edge colorings are obtained by classical polynomial methods (see [WER 97]), but for common multigraphs, the k-coloring of edges problem is NP-complete.
While the k-coloring problem of the edges of a multigraph G can always be reduced to a k-coloring problem of the vertices of an associated graph L(G), there are however variations on the edge coloring model arising in scheduling problems that cannot be reduced naturally to a vertex coloring model. We will give an overview of a few of these variations.
10.13.1. f-Coloring of edges
Models of coloring edges of a multigraph arise in the technological domain. Let us consider the problem of transferring files in a computer network. Let there be a set X of computers, each one capable of communicating directly with every other one, and a set E of large files that must be transferred between various computers. Each computer υ ∈ X has f(υ) identical ports that allow it to manage up to f(υ) transfers at any given moment. Here we assume that each file is transferred directly from its origin to its destination, that once a transfer has started, it carries on without interruption, and that all the transfers require the same time. The aim is to find a scheduling of the transfers in such a way as to minimize the total time required to carry out all the transfers.
This problem can be modeled with the help of a multigraph Gf = (X, E, f) whose vertices represent the computers and where each file is represented by an edge that joins the two computers concerned with the file. Finding a schedule that minimizes the total time then comes down to finding an assignment of a minimum number 
of colors to the edges of Gf in such a way that for each vertex v and each color i, we have |Ci(v)| f(v), where Ci(v) is the set of the edges of color i that are incident to v. This problem is known as f-coloring of the edges.
Since the special case where f(v) = 1 for every computer v comes down to establishing the chromatic index of Gf, the f-color of the edges problem is in general hard. But in the situation where each computer only has files to send, or only files to receive (that is the associated multigraph Gf is bipartite), the problem can be solved in polynomial time [COF 85].
For a graph Gf = (X, E, f), let d(v) be the degree of v in Gf and:
We then clearly have 
. By considering the chromatic index problem on a secondary graph constructed from Gf, we can show that 
when Gf is a simple graph [ZHO 00]. For bipartite multigraphs and for simple planar graphs such that Δf(Gf) 8, we have 
.
Many variations and generalizations of the file transfer problem, including, for example, transfer times that depend on the size of files, or considering the absence of a central controller that constructs the schedule, are studied in [COF 85].
10.13.2. [g, f]-Colorings of edges
In the file transfer problem, the function f allows us to restrict the number of files that a computer can receive and send at any given moment. If we wish to balance the transfer process, we can require that at any moment at least g(v) ports of the computer v are used for a transfer. This new problem can be modeled with the help of the [g, f]- coloring of edges problem (in k colors) on a multigraph Gg,f = (X, E, g, f). This consists of assigning a color (from the k available ones) to each edge of Gg,f in such a way that g(v) |Ci(v)| f(v) for every vertex v ∈ X and every color i. The [g, f]-coloring of edges problem is also known as the [g, f]-factorization problem.
For every [g, f]-coloring of the edges of a multigraph Gg,f in k colors, we have:
In an equivalent way, a multigraph Gg,f does not have a [g, f]-coloring of the edges in k colors if a vertex v exists such that:
Certain conditions allow us to ensure the existence of a [g, f]-coloring of the edges in k colors of a graph.
PROPERTY 10.15.– [HIL 94] Let there be a simple graph Gg,f = (X, E, g, f) such that the vertices v for which g(v) = f(v) are pairwise non-adjacent, and such that k·g(w) + 1 d(w) k·f(w) − 1 for the other vertices w (with k 2). Then Gg,f has a [g, f]-coloring of the edges in k colors.
A coloring in k colors of the edges of a graph G is said to be equitable if we have ||Ci(v)| − |Cj(v)|| 1 for each vertex v of G, and 1 i j k. In the special case where:
for every vertex v, a [g, f]-coloring of Gg,f is an equitable coloring and the previous property becomes corollary 10.1.
COROLLARY 10.1.– [HIL 94] Let there be a simple graph G = (X, E) such that the vertices v for which k divides d(v) are pairwise non-adjacent. Then G has an equitable edge coloring in k colors.
Note that even if a graph does not have an equitable coloring of the edges in k colors it nevertheless has an “almost equitable” coloring of the edges in k colors [HIL 94], where ||Cp(v)| − |Cq(v)|| = 2 for at most one couple of colors {p, q}, and ||Ci(v)| − |Cj(v)|| 1 for all the other couples of colors {i, j} ≠ {p, q}.
Polynomial (sequential and parallel) algorithms for the [g, f]-coloring of edges problem on various classes of graphs are presented in [ZHO 00].
10.13.3. A model of hypergraph coloring
We are going to examine a more general coloring model than those presented up to now since this will lead us to use the concept of hypergraphs already mentioned.
Let us consider a timetable construction problem. As at the start of the section, we have a set M of teachers mi, a set C of classes (groups of pupils) cj, and a collection E of lectures (that last one hour), characterized by a couple [mi, cj]. We associate with this problem a bipartite multigraph G = (M, C, E). A timetable in k periods is represented by a k-coloring of the edges of G.
Let us now assume that as well as the lectures in E, we have lectures given by one teacher to several classes simultaneously (this occurs in some teaching institutions, for example foundation lectures in university courses).
To simplify the notation, we allow the classes to be partitioned into a certain number of groups G1,…, Gp (each class therefore belongs to exactly one group; each group has at least one class). This model was introduced and studied in [ASR 02] and [WER 02].
A certain number of lectures must be given by a teacher mi to a group Gl; each of these lectures will be represented by a hyperedge that contains the vertex mi as well as all the vertices cj such that cj ∈ Gl. The graph G is transformed in this way into a hypergraph H; as before, there is a biunivocal correspondence between timetables in k periods and k-colorings of edges of H, that is the partitions of the set of the edges and hyperedges of H into sets M1,…, Mk of (hyper)edges called matchings (each Mr is a collection of pairwise disjoint edges).
Figure 10.11 gives an example of such a timetabling problem with group lectures (here we would have G3 = {c5} and G4 = {c6} but we will not mention these trivial groups).
In a hypergraph H, as in graphs, we can define the degree dH(v) of a vertex v as the number of edges that contain the vertex v. Δ(H) will be the maximum degree of the vertices of H. In the example dealt with, we have Δ(H) = 3 (see Figure 10.12): no one teacher is involved in more than three lectures and similarly no one class has to attend more than three lectures. Figure 10.13 gives a timetable of minimum duration t for this problem; here we have t = 4 > ΄(H) = 3, contrary to what happened in the case where there were no groups of classes. Establishing the minimum duration is less simple than in the case of bipartite multigraphs. The complexity of the timetabling with groups problem was studied in [ASR 02] and in [WER 02]. Note that this model can be applied to task scheduling problems (where instead of teachers and classes, we have tasks and processors, with each task being executed on the various processors, in any order, but for fixed durations).
Figure 10.11. An example of a timetabling problem with group lectures
Figure 10.12. The hypergraph H associated with the problem in Figure 10.11
Contrary to what is allowed for timetabling problems (where each lecture is given for 60 consecutive minutes), running operations can, in certain cases, be interrupted and continued later on with the aim of reducing the total execution time.
Thus in the example in Figure 10.11, if we allowed the lectures in progress to be interrupted (after 30 minutes for example), we could obtain the timetable given in Figure 10.14; this one has a total duration t = 3.5 < 4 !
This type of solution with interruptions is nevertheless also of great interest in the case of school timetables: by doubling all the durations (each half hour is considered as being a period of one hour), from the timetable in Figure 10.14 we obtain a timetable that places all the lectures that need to be given during an interval of two weeks that lasts seven hours (instead of the eight hours that we would have by using the timetable from Figure 10.13 for two consecutive weeks).
Figure 10.13. A timetable of minimum duration for the example in Figure 10.11
Figure 10.14. A timetable (with interruptions allowed) with t = 3, 5
The above example shows that it is sometimes worthwhile considering extensions of vertex coloring that are fractional colorings. These are defined by going back to the basic model of vertex coloring in order to simplify the notations and the presentation.
Let us consider a graph G = (V, E) with n vertices and let M be a matrix with n lines whose columns represent all the inclusionwise maximal stable sets of G. Let p be the number of columns of M. The problem of finding the chromatic number of G can then be written as:
Indeed, we have xj = 1 if the stable set Sj is used in the coloring and xj = 0 if not; the constraints assert that each vertex is covered by at least one of the stable sets kept in the coloring and the objective function counts the number of colors used.
If the integrality constraint on 
is replaced by 
then we have a common linear programming problem and we consider fractional colorings; this is what was done in the above timetabling problem: certain matchings Mj (that correspond to the stable sets Sj in the graph L(H) associated with H) were used with a coefficient xj = 1/2. The study of fractional colorings and integrality properties specific to certain classes of matrices M has been the subject of many studies (for a complete presentation, see [SCH 03]).
10.14. Conclusion
Real problems that are formulated in terms of graph coloring often involve graphs of large size. Some papers seem to show that many graphs that come from real problems are one-perfect (a graph G is one-perfect if χ(G) = ω(G)), which leads to extremely effective vertex coloring algorithms that allow us to find an optimal coloring in a few seconds for graphs with several thousand vertices [COU 97]. But for random graphs, or for tackling various variations on the coloring problem, it is necessary to find more effective algorithms than those that currently exist for these large graphs. Indeed, the Tabu search requires a prohibitive calculation time for these. In these cases, evolutionary algorithms can be useful. These algorithms have met with great success in combinatorial optimization in the last few years, but their performances are very variable. The best-known evolutionary algorithms are genetic algorithms, we will describe their general principle.
Unlike the Tabu search in which there is only one current solution which is modi-fied as the iterations are made, genetic algorithms manage a set (called a population) of solutions (called individuals). With each iteration (“generation”), couples of individuals are selected (giving preference to the good quality solutions with regards to the objective function), and the two individuals of a couple are used to create one or more new individuals. These generally undergo another random modification (analogous to a mutation) or, even better, are improved with the help of an iterative algorithm, for example of the Tabu type. The new current population is made up of individuals chosen from the previous population and these new individuals.
For the common coloring problem, an individual is a partition of the set of the vertices and the objective function is still the one used in the Tabu algorithm. We therefore once more seek a partition s such that f(s) = 0. On the basis of two partitions 
and 
, a new partition 
can be created in the following way. Let us consider a vertex v that is found in the set 
of the partition s1, and in the set 
of the partition s2: in s′, v will be placed in the set 
or 
depending on the number of neighbors that it has in 
and 
. More details are given in [FLE 96], where the following evolutionary algorithm is proposed:
– choose an initial population 
;
– s* := best individual of ;
– i := 0 (iterations number counter);
– while no stopping criteria are satisfied do:
- i := i + 1;
- select four individuals s1 to s4 from ;
- create 
on the basis of s1 and s2;
- create 
on the basis of s3 and s4;
- apply the Tabu algorithm to 
and 
;
- add 
and 
to ;
- remove the two worst individuals from ;
- if f(best individual in ) < f(s*) then s* := best individual of .
While this algorithm is not competitive with regard to a Tabu search, it is nonethe-less useful for random graphs with 500 vertices and more (density 0.5). Indeed, this algorithm is more robust than the Tabu search on the residual graphs mentioned in section 10.5 (see [FLE 96]).
However, better ways of creating an individual on the basis of two other individuals (or even more) could lead to more effective algorithms. Finding such an operator, as well as developing good heuristic algorithms for various generalizations and variations of the coloring problem, make up an important research direction in the graph coloring domain.
Finally, let us mention another coloring problem solution method that is very different to all those mentioned up until now: DNA computing. This solution method, which is applicable to many combinatorial problems, was first proposed for the traveling salesman problem [ADL 94], but was then adapted to the graph coloring problem with k = 3 colors [AMO 96, BAC 96]. In general, DNA computing consists of making an explicit enumeration of the set of solutions of the problem being studied by manipulating strands of DNA in a laboratory. These strands are synthesized in such a way as to encode the possible solutions of the problem, then the non-optimal solution(s) are removed using molecular biology techniques in order to have only the optimal solution(s) at the end of the manipulations. But despite the small size of DNA molecules, the exponential growth of the number of possible solutions with the size of the problem limits the size of the instances that can be solved using this approach. In the case of the graph coloring problem, it is scarcely possible to consider graphs with more than 30 vertices with current techniques [LIU 02], which puts in doubt the future prospects of this method.
10.15. Bibliography
[ADL 94] ADLEMAN L., “Molecular computation of solutions to combinatorial problems”, Science, vol. 266, p. 1021–1024, 1994.
[ALO 92] ALON N., TARSI M., “Colorings and orientations of graphs”, Combinatorica, vol. 12, p. 125–134, 1992.
[AMO 96] AMOS M., GIBBONS A., HODGSON D., “Error-resistant implementation of DNA computations”, Proc. of the 2nd Annual Meeting on DNA Based Computers, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, p. 151–161, 1996.
[ASR 02] ASRATIAN A., DE WERRA D., “A generalized class-teacher model for some timetabling problems”, European J. of Operational Research, vol. 143, p. 531–542, 2002.
[BAC 96] BACH E., CONDON A., GLASER E., TANGUAY C., “DNA models and algorithms for NP-complete problems”, Proc. of the 11th Annual IEEE Conference on Computational Complexity, p. 290–300, 1996.
[BEL 98] BELLARE M., GOLDREICH O., SUDAN M., “Free bits, PCPs and non-approximability – towards tight results”, SIAM J. Computing, vol. 27, p. 804–915, 1998.
[BER 83] BERGE C., Graphes, Gauthier-Villars, Paris, 1983.
[BER 84] BERGE C., CHVÁTAL V., Eds., Topics on Perfect Graphs, vol. 21 of Annals of Discrete Mathematics, 1984.
[BER 87] BERGE C., Hypergraphes, Gauthier-Villars, Paris, 1987.
[BIR 92] BIRÓ M., HUJTER M., TUZA Z., “Precoloring extension. I. Interval graphs”, Discrete Mathematics, vol. 100, p. 267–279, 1992.
[BLÖ 03] BLÖCHLIGER I., ZUFFEREY N., A reactive tabu search using partial solutions for the graph coloring problem, Report, Swiss Federal Institute of Technology, Lausanne, 2003.
[BOD 94] BODLAENDER H., JANSEN K., WOEGINGER G., “Scheduling with incompatible jobs”, Discrete Applied Mathematics, vol. 55, p. 219–232, 1994.
[CHU 02] CHUDNOVSKY M., ROBERTSON N., SEYMOUR P., THOMAS R., The Strong Perfect Graph Theorem, Report, Georgia Institute of Technology, Atlanta, 2002.
[CHV 84] CHVÁTAL V., “Perfectly ordered graphs”, Topics on Perfect Graphs, vol. 21 of Annals of Discrete Mathematics, p. 63–65, 1984.
[COF 85] COFFMAN JR E., GAREY M., JOHNSON D., LAPAUGH A., “Scheduling file transfers”, SIAM Journal on Computing, vol. 14, p. 744–780, 1985.
[COU 93] COURCELLE B., ENGELFRIET J., ROZENBERG G., “Handle-rewriting hypergraphs grammars”, J. of Computer and System Sciences, vol. 46, p. 218–270, 1993.
[COU 97] COUDERT O., “Exact coloring of real-life graphs is easy”, Proc. of 34th ACM/IEEE Design Automation Conf., ACM Press, New York, p. 121–126, 1997.
[DUB 93] DUBOIS N., DE WERRA D., “EPCOT: an efficient procedure for coloring optimally with Tabu search”, Computers and Mathematics with Applications, vol. 25, p. 35–45, 1993.
[FLE 96] FLEURENT C., FERLAND J., “Genetic and hybrid algorithms for graph coloring”, LAPORTE G., OSMAN I., Eds., Metaheuristics in Combinatorial Optimization, vol. 63 of Annals of Operations Research, p. 437–461, 1996.
[GAL 83] GALIL Z., LEVEN D., “NP-completeness of finding the chromatic index of regular graphs”, Journal of Algorithms, vol. 4, p. 35–44, 1983.
[GAR 76a] GAREY M., JOHNSON D., “The complexity of near-optimal graph coloring”, Journal of the ACM, vol. 23, p. 43–49, 1976.
[GAR 76b] GAREY M., JOHNSON D., STOCKMEYER L., “Some simplified NP-complete graph problems”, Theoretical Computer Science, vol. 1, p. 237–267, 1976.
[GLO 97] GLOVER F., LAGUNA M., Tabu Search, Kluwer Academic Publishers, Dordrecht, 1997.
[GOL 84] GOLUMBIC M., Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1984.
[GRÖ 88] GRÖTSCHEL M., LOVASZ L., SCHRIJVER A., Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, Berlin, 1988.
[HAL 93] HALLDÓRSSON M., “A still better performance guarantee for approximate graph coloring”, Information Processing Letters, vol. 45, p. 19–23, 1993.
[HAN 93] HANSEN P., HERTZ A., KUPLINSKY J., “Bounded vertex colorings of graphs”, Discrete Mathematics, vol. 111, p. 305–312, 1993.
[HAN 97] HANSEN P., KUPLINSKY J., DE WERRA D., “Mixed graph coloring”, Mathematical Methods of Operations Research, vol. 45, p. 145–160, 1997.
[HER 02] HERRMANN F., HERTZ A., “Finding the chromatic number by means of critical graphs”, ACM Journal of Experimental Algorithmics, vol. 7/10, p. 1–9, 2002.
[HIL 94] HILTON A., DE WERRA D., “A sufficient condition for equitable edge-colourings of simple graphs”, Discrete Mathematics, vol. 128, p. 179–201, 1994.
[HOL 81] HOLYER I., “The NP-completeness of edge-coloring”, SIAM Journal on Computing, vol. 10, p. 718–720, 1981.
[INS] INSTITUT FÜR THEORETISCHE INFORMATIK, Information System on Graph Class Inclusions, http://wwwteo.informatik.uni-rostock.de/isgci/index.html.
[KOB 03] KOBLER D., ROTICS U., “Edge dominating set and colorings on graphs with fixed clique-width”, Discrete Applied Mathematics, vol. 126, p. 197–221, 2003.
[LAW 76] LAWLER E., Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, New York, 1976.
[LEI 79] LEIGHTON F., “A graph coloring algorithm for large scheduling problems”, Journal of Research of the National Bureau of Standards, vol. 84, p. 742–774, 1979.
[LIU 02] LIU Y., XU J., PAN L., WANG S., “DNA solution of a graph coloring problem”, Journal of Chemical Information and Computer Sciences, vol. 42, p. 524–528, 2002.
[MID 90] MIDDENDORF M., PFEIFFER F., “On the complexity of recognizing perfectly or-derable graphs”, Discrete Mathematics, vol. 80, p. 327–333, 1990.
[PNU 71] PNUELI A., LEMPEL A., EVEN S., “Transitive orientation of graphs and identification of permutation graphs”, Canadian Journal of Mathematics, vol. 23, p. 160–175, 1971.
[ROB 76] ROBERTS F., Discrete Mathematical Models, Prentice-Hall, Englewood Cliffs, 1976.
[SCH 03] SCHRIJVER A., Combinatorial Optimization: Polyhedra and Efficiency, Springer-Verlag, Berlin, 2003.
[TUZ 97] TUZA Z., “Graph colorings with local constraints — a survey”, Discussiones Math-ematicae Graph Theory, vol. 17, p. 161–228, 1997.
[VIZ 64] VIZING V., “On an estimate of the chromatic class of a p-graph (in Russian)”, Metody Discret Analiz., vol. 3, p. 25–30, 1964.
[WEL 67] WELSH D., POWELL M., “An upper bound on the chromatic number of a graph and its application to timetabling problems”, Computer Journal, vol. 10, p. 85–87, 1967.
[WER 88] DE WERRA D., HERTZ A., “Consecutive colorings of graphs”, Zeitschrift für Operations Research, vol. 32, p. 1–8, 1988.
[WER 94] DE WERRA D., GAY Y., “Chromatic scheduling and frequency assignment”, Discrete Applied Mathematics, vol. 49, p. 165–174, 1994.
[WER 97] DE WERRA D., “The combinatorics of timetabling”, European Journal of Operational Research, vol. 96, p. 504–513, 1997.
[WER 99a] DE WERRA D., “On a multiconstrained model for chromatic scheduling”, Discrete Applied Mathematics, vol. 94, p. 171–180, 1999.
[WER 99b] DE WERRA D., EISENBEIS C., LELAIT S., MARMOL B., “On a graph-theoretical model for cyclic register allocation”, Discrete Applied Mathematics, vol. 93, p. 191–203, 1999.
[WER 02] DE WERRA D., ASRATIAN A., DURAND S., “Complexity of some special types of timetabling problems”, Journal of Scheduling, vol. 5, p. 171–183, 2002.
[WER 03] DE WERRA D., KOBLER D., “Coloration et ordonnancement chromatique”, RAIRO Operations Research, vol. 37, p. 29–66, 2003.
[ZHO 00] ZHOU X., NISHIZEKI T., “Graph coloring algorithms”, IEICE Trans. on Information and Systems, vol. E83-D, p. 407–417, 2000.
1 Chapter written by Dominique DE WERRA and Daniel KOBLER.