Project 8: Graph Coloring and Scheduling

A coloring of a graph, sometimes called a vertex coloring, is an assignment of colors to the vertices of a graph such that no edge in the graph has the same-colored endpoints. The coloring of the graph on the left is a valid coloring, as each of the five edges has different colored endpoints, but the coloring of the graph on the right is not a valid coloring, since the diagonal edge connects two yellow vertices.

The chromatic number of a graph G is the smallest number of colors required to construct a valid coloring of the graph, designated by χ(G) (a lowercase Greek letter chi, pronounced “kai”). Notice that the chromatic number of a bipartite graph will always be two, as long as the graph has at least one edge.

Consider a scheduling problem where you have v classes to schedule and n different time slots during the week. Each class has an enrollment of students, and most students take multiple classes. No student may be in two classes at the same time, so the challenge is to schedule the classes in a way that no student has a conflict. For example, consider the following six classes to the left.

To model this is a graph coloring problem, create a node for each course. In this case, label the courses, M, N, P, Q, R, and S. Then, for each pair of courses that have at least one student in common, add an edge between the two course nodes. Since Alex is in Mathematics and Nursing, we need to add an edge between nodes M and N.

Now, find a valid coloring for the graph. Each color corresponds to a different time slot, and a valid graph coloring will make sure that no two courses connected by an edge will have the same color, meaning that no two classes that have the same student will be scheduled at the same time. This example requires four colors, so therefore, four different time periods are needed to create a conflict-free schedule for the students.

Of course, if the chromatic number for the graph is higher than n, the number of different time slots available during the week, there will be no way of finding a schedule to satisfy every student.