RESTRICTIONS AND PREASSIGNMENTS IN PREEMPTIVE OPEN SHOP SCHEDULING

Preemptive open shop scheduling can be viewed as an edge coloring prob lem in a bipartite multigraph. In some applications, restrictions of c olors (in particular preassignments) are made for some edges. We give characterizations of graphs where some special preassignments can be e mbedded in a minimum coloring (number of colors = maximum degree). The case of restricted colorings of trees is shown to be solvable in poly nomial time.