Restricted coloring models for timetabling Original Research Article

We consider some node coloring problems with additional requirements which occur in timetabling and in chromatic scheduling; in these colorings, each node v must get one color chosen in a set ϕ(v) of feasible colors and the cardinalities of the color classes must not exceed some given bounds. We characterize the cases where the constraint matrix is perfect, balanced or totally unimodular and we review some results in the area as well as extensions and variations.