On a multiconstrained model for chromatic scheduling

A graph coloring model is described for handling some types of chromatic sc heduling problems. Applications in school timetabling for instance as well as in robotics suggest to include additional requirements like sets of feas ible colors for each node of the associated graph and upper bounds on the c ardinalities of the color classes. Necessary conditions for the existence o f solutions are given and cases where these conditions are sufficient will be characterized. (C) 1999 Published by Elsevier Science B.V. All rights re served.