Preassignment requirements in chromatic scheduling Original Research Article

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