by Sotskov, Y.N., Tanaev, V.S., Werner, F..
Series: 1998-38, Preprints
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.
scheduling, mixed graph, vertex coloring, chromatic polynomial
This paper was published in:
Optimization, Vol. 51 (3), 2002, 597 - 624.