Graph Coloring Conditions for the Existence
of Solutions to the Timetable Problem

A necessary and sufficient condition is presented
for the existence of a solution to the Gotlieb 
class-teacher timetable problem.  Several relationships
are established between the class-teacher timetable 
problem and graphs with preconditions.  These preconditions
place additional restrictions on the coloration 
of a graph.  The preconditions correspond to the unavailability
constraints and preassigned meetings 
in the class-teacher timetable problem.  Using some recent
results that convert graphs with preconditions 
to graphs without them, it is shown that the existence
of a coloration of a graph is the required necessary 
and sufficient condition.

CACM August, 1974

Neufeld, G. A.
Tartar, J.

graphs, coloration, preassignment, prevention
of assignment, class-teacher timetables

3.9 5.30 5.32 5.59

CA740805 JB January 17, 1978  9:55 AM

1355	4	2619
2619	4	2619
2619	4	2619
2772	4	2619
2787	4	2619
1419	5	2619
1429	5	2619
2619	5	2619
2619	5	2619
2619	5	2619