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.