EXAMPLE 5 Scheduling Examinations
Small State is offering eight courses during its summer session. The table shows with an X which pairs of courses have one or more students in common. Only two air-conditioned lecture halls are available for use at any one time. To design an efficient way to schedule the final examinations, we can represent the information in this table by using a graph, as shown in Figure 3.22a. In the graph, courses are represented by vertices and two courses are joined by an edge if there is any student enrolled in both courses.
| French () | X | X | X | X | X | |||
| Mathematics | X | X | X | |||||
| History | X | X | X | |||||
| Philosophy | X | X | ||||||
| English | X | X | X | |||||
| Italian | X | X | X | X | X | |||
| Spanish | X | X | ||||||
| Chemistry | X | X | X |
101
We are faced with the following graph theory problem: Can we assign labels to the vertices of the graph in such a way that vertices that are joined by an edge get different labels? We think of the labels as the time slots the courses are assigned for final examinations. Traditionally, in graph theory such labels are referred to as colors. In this language, we seek to color the vertices of the graph so that vertices that are joined by an edge get different colors. Such a coloring is called a vertex coloring.
Vertex Coloring DEFINITION
The vertex coloring problem for a graph requires assigning each vertex of the graph a color (label) such that two vertices joined by an edge are assigned different colors.
Figure 3.22b shows one way to color the vertices of the graph so that each vertex gets a different color. Note that numbers are being used to represent the different colors. This solution is not very valuable, however, because it means that each course must be given its own time slot.
Can we improve upon eight colors? Note that , and the edges that join them form a complete graph on four vertices. To have the vertices that are joined by an edge colored differently, we must assign , and four different colors because each of these four vertices is joined to the other three (see Figure 3.22c). Thus, any coloring of the graph in Figure 3.22a must use at least four colors. Exactly four colors will do, because the four colors used for , and can be used to color the remaining vertices while ensuring that no two vertices joined by an edge have the same color. The improved coloring in Figure 3.22c was found by trial and error.
Chromatic Number DEFINITION
The chromatic number is the minimum number of colors (labels) needed to label the vertices of a graph so that no two vertices of the graph joined by an edge get the same color.
The examination graph we have been studying has chromatic number 4; hence, we can schedule the eight examinations in four time slots without a conflict. Notice, however, that the coloring in Figure 3.22c schedules three different courses for the time slot corresponding to color 2. This means that not enough rooms with air conditioning will be available. Is there a way to recolor the graph with four colors so that each of the four colors is used only twice? Figure 3.22d shows that the answer is “yes.”
Thus, we are able to schedule the eight final examinations in four time slots, using only two air-conditioned rooms, and no student will have a conflict under this schedule!
102
