Chromatic Scheduling and the Chromatic Number Problem

The chromatic scheduling problem may be defined as any problem in which the solution is a partition of a set of objects. Since the partitions may not be distinct, redundant solutions can be generated when partial enumeration techniques are applied to chromatic scheduling problems. The necessary theory is developed to prevent redundant solutions in the application of partial enumeration techniques to chromatic scheduling problems with indistinguishable partitions and distinct objects. The chromatic number problem, which is the problem of finding the chromatic number of any graph, is a particular case of the chromatic scheduling problem. Two algorithms, basic and look-ahead, are developed for the chromatic number problem. Computational experience is given for each algorithm.