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