PREASSIGNMENT REQUIREMENTS IN CHROMATIC SCHEDULING

In open shop and class-teacher timetabling problems preassignment requ irements are often present; they are represented by precolorings in th e graphs associated with the models. We consider the problem of extend ing a precoloring to an edge k-coloring of the whole graph (where k is fixed) and we describe some polynomially solvable cases of this probl em which is generally NP-complete. A model with cost is given and we s how that for trees it can be solved in polynomial time.