ERCIM News No.44 - January 2001 [contents]

On-line Graph Coloring

by Jenö Lehel

Many variants of time tabling, sequencing, scheduling, and allocation problems boil down to the fundamental problem of partitioning a collection of objects into families according to certain requirements. Members of the Discrete Structures Group at SZTAKI initiated a natural model for a certain type of these practical questions in terms of chromatic graph theory.

The scheduling of a set of tasks on parallel machines is a basic problem in combinatorial optimization. In certain applications, tasks are to be scheduled promptly and irrevocably without the complete knowledge of the input stream. The case in which a task must be processed in an uninterrupted fashion (the non-preemptive model), the scheduling on k machines becomes a question of coloring intervals or interval graphs on-line with k colors. An equivalent scenario of dynamic storage allocation due to Marek Chrobak and Maciej Slusarek, motivated us to introduce the notion of on-line coloring and on-line chromatic number of graphs or, more generally, families of graphs different from interval graphs. The research of the author with András Gyárfás (SZTAKI) and Zoltán Király (Loránd Eötvös University, Budapest) in this area over the last decade contributed to the development of classical graph theory with several noteworthy results and challenging open problems. Furthermore, it seems to have a certain impact on the theory of on-line algorithms, a recently outgrowing branch of combinatorial optimization.

The on-line chromatic number of a graph G is usually defined through a two-person game. The Drawer presents the vertices of G in some order together with adjacencies to vertices already given. The Painter assigns a legal color (positive integer) to the current vertex given. The aim of the Drawer is to force the Painter to use as many colors as possible and the aim of the Painter is to use as few colors as possible. The common optimal value is the on-line chromatic number of G. The most familiar on-line coloring algorithm is the First Fit (alias Greedy) algorithm which assigns the smallest proper color to the current vertex.

An on-line coloring algorithm is called on-line competitive against a graph family if there exists an upper bound on its performance in terms of the on-line chromatic number of the graphs in the family. Intuitively, it is a universal on-line algorithm with reasonable performance on every member of the graph family.

Against some graph families, for example against the family of trees, the First Fit coloring algorithm is an on-line competitive algorithm. However, this property does not hold in general: against the family of on-line 3-colorable bipartite graphs the First Fit algorithm is not on-line competitive.

An example shows that an on-line competitive algorithm against the family of 3-colorable bipartite graphs must use at least four colors: just consider the pair of graphs B and E in the Figure. The reader can easily check that each graph is on-line 3-colorable but the hint in the Figure indicates that 4 colors are needed if the Painter does not know in advance which one is presented by the Drawer, B or E. It turned out that this elementary example is the best possible one, moreover, there exists an on-line competitive algorithm using at most four colors against the family of all on-line 3-colorable ghraphs.

Many results in the theory of on-line graph colorings can be formulated in terms of on-line competitive algorithms. Some of these results demonstrate that against certain families of graphs these algorithms are competitive in a stronger sense (compared with off-line ones). The main open problem concerning on-line competitive algorithms is to decide whether there exists an algorithm like this against the family of on-line k-colorable graphs, for any fixed k. The answer is not even known for special graph families like the families of bipartite graphs, chordal graphs or even chordal bipartite graphs.

In addition to contributing to the development of recursive combinatorics, our research inspired some results of experts eg Hal Kierstead and William Trotter. Their earlier deep results on partially ordered sets have got a new interpretation in terms of on-line partitioning or coloring algorithms of graphs. The concept of on-line algorithms combined with graph theory turned to be a steady source of challenging new problems and led to a number of interesting graph theory results obtained by several competitive research groups. Our group is open for any further discussions.

Please contact:
Jenö Lehel - SZTAKI and University of Louisville
Tel:+ 36 1 4665 644
E-mail: lehel@louisville.edu