Zurück zu den Preprints des Jahres 1998


1998-38

Scheduling problems and mixed graph colorings

by Sotskov, Y.N., Tanaev, V.S., Werner, F..


Series: 1998-38, Preprints

MSC:
90B35 Scheduling theory, deterministic
05C15 Coloring of graphs and hypergraphs

Abstract:
Some scheduling problems induce a mixed graph coloring, i.e. an assignment
of positive integers (colors) to vertices of a mixed graph
such that, if two vertices are joined by an edge, then their colors have to be
different, and if two vertices are joined by an arc, then the color of the startvertex has to be not greater than
the color of the endvertex. We discuss some algorithms for coloring the vertices of a mixed graph with a small number t
of colors and present computational results for calculating the chromatic number, i.e. the minimal possible
value of such a t. We also study the chromatic polynomial of a mixed graph which may be used for calculating
the number of feasible schedules.

Keywords:
scheduling, mixed graph, vertex coloring, chromatic polynomial

This paper was published in:
Optimization, Vol. 51 (3), 2002, 597 - 624.