Dominique de Werra

Title of Presentation: Variations and Extensions of Coloring

APORS 2006

Manila, Philippines

January 16, 2006

Abstract:

Because of its many applications, graph coloring models have become one of the most studied problems in combinatorial optimization. Applications have in addition provided strong motivation to extend the coloring models in various directions.

The basic graph coloring model consists in finding whether for a given integer k and for a given graph G = (V,E) one can partition the vertex set V into subsets V1, V2, . . . , Vk where no two vertices in any Vi are linked byan edge (each Vi is a stable set).

Besides courses scheduling, frequency assignment in telecommunication networks has often been formulated and solved by using graph coloring pro- cedures. But these basic models are generally not sucient to handle real life problems even in their simplified versions.

Various extensions of these models have been proposed; a first idea is to define a coloring in a (partially) oriented graph; this is quite natural since there is a close connection between colorings and orientations in a graph: the vertices of an (unoriented) graph can be colored with k colors if and only if the edges of the graph can be given an orientation such that the resulting graph has no oriented circuit and no oriented path with more than k vertices. For coloring a (partially) oriented graph we will use an ordered set of colors, say {1, 2, . . . , k} and the rule will be to give different colors to thetwo endvertices of an edge and to give colors c(x), c(y) with c(x) < c(y) to vertices x, y that are the initial and the terminal vertex of an arc (x,y). Such a model occurs in scheduling when there are jobs that may have some requirements on the order in which they are processed or some incompatibility (non simultaneity) constraints: colors correspond to time periods and an arc (x, y) means that job x must be processed before job x can start. This type of coloring (called mixed graph coloring) has been studied and bounds on the minimum number of colors (called chromatic number) have been derived.

In the above model every vertex gets exactly one color, which means that all jobs have the same processing time. In order to be able to deal with more general situations, one has to consider that every vertex x has a weight w(x), so that if w(x) corresponds to the processing time of the associated job, vertex x will receive not one but an interval of w(x) consecutive colors; this will translate the fact that its processing will require w(x) time units; the requirement will be that if x, y are linked by an edge, the corresponding intervals of colors should not intersect.

For an arc x, y, the interval of x should be on the left of the interval of y. Such colorings have naturally been called interval colorings; again bounds on the “interval chromatic number” have been derived and coloring procedures have been developed.

Such assignments of weights to the vertices of a graph have in fact given rise to several variations of weighted colorings motivated by applications. In some industrial processes (such as production of some types of electronic components), one has to process a collection of jobs that may be subject to some incompatibilities defined between pairs of jobs. So one has to divide the set of all jobs into several batches of pairwise compatible jobs. The batches are processed one after the other and the processing time of a batch (of jobs processed in parallel) will be given by the maximum weight (i.e., processing time) of the jobs in this batch. It is then required to minimize the sum of the completion times of the various batches. This model has also been studied and results on its approximability have also been obtained, which give a bound of the performance rate of some coloring techniques. Batch scheduling with pairwise incompatibilities occurs also in some com- munication systems by satellite; it is here also interesting to see how these models are used in very di erent contexts as soon as they are available. Another type of extension of the basic coloring should be mentioned here: if we have a k-coloring in a graph G, in the complement graph G of G (where two vertices are linked if and only if they are not linked in G), it corresponds to a partition of the vertex set V into k cliques (i.e., a set of vertices that are all linked).

A natural way of extending the concept of vertex k-coloring (with k stable sets) would be to find whether G has a partition V1, . . . , Vk of its vertex set V where each Vi is a clique or a stable set. This has also been studied under the name of cocoloring. It turns out that such a model has some applications in a special problem of robotics, or more precisely of inventory storage. A collection of items is arranged in an arbitrary order along a storage corridor; they have di erent sizes and robots have to pick up all these items with the requirement that each robot constructs a pile of items by taking first the largest ones and putting smaller ones on top of its pile. It is required to minimize the number of trips of robots (from the entry point located at the end of corridor, through the corridor and back to the entry point) to pick up all items.

It can be seen that this corresponds to a coloring close to the above type where the items collected in a single two-way trip correspond to a special graph formed by a clique and a stable set.

These models will be presented and discussed in the talk.

References related to various applications of colorings can be found in [1].

References

[1] D. de Werra and D.Kobler, Colorations de graphs: fondements et appli- cations, RAIRO 37, (2003), 29-66.

Bio

Dominique de Werra got an Engineering Diploma in Physics from the Ecole Polytechnique Federale de Lausanne in 1965 and a Ph.D. in Operations Research from this institution. He was then assistant professor in the Dept of Management Sciences of the University of Waterloo (Ontario) and later associate professor of Operations Research at EPFL where he was the first professor of O.R. He has been a visiting professor at various European, American and Asian Universities. He was president of the Swiss Operational Research Society in 1985-1986 and President of EURO, the European Association of Operational Research Societies (10’000 members) in 1987-1988.

He has honorary degrees from University of Paris-Dauphine and from the Technical University of Poznan (Poland). He is co-founder of the ECCO Conferences (European Chapter on Combinatorial Optimization) and associate editor of various scientific journals (Discrete Applied Maths (USA), Annals of OR (USA), European Journal of Operational Research, Discrete Optimization, etc.).

He was vice-president of EPFL in charge of education between 1991 and 2000. He is a member of several strategic orientation committees (Ecole des Mines de France, etc.).

He has supervised a number of Ph. thesis at EPFL and published over 180 papers in refereed journals of O.R., Combinatorial Optimization, Graph Theory, Scheduling, Timetabling.

He was awarded in 1995 the EURO Gold Medal for his contributions to O.R. and to its development in Europe.

Between 2000 and 2005, he was Dean of international relations of EPFL and from 2000 to 2003 he was President of the CLUSTER (Consortium Linking Universities of Science and Technology for Education and Research) network grouping 11 of the best European universities of technology.

From 2000 on he is a member of the scientific council of the OAQ (office for accreditation and quality assurance) of the Swiss Confederation.