## Colorful Mathematics: Part IV

3. Resolving conflicts (II)

We have seen how, using a graph-coloring model, we can assist in the scheduling of committees to avoid scheduling committee members in two places at once in the minimum number of time slots. Just as in "theoretical" mathematics, applied mathematicians seek ways to generalize or specialize results that they have proven, building on success in solving a problem to try to solve similar problems in related situations.

We seek situations where we can use a graph model to represent objects and join two of these objects when we want to "avoid a conflict." For example, the scheduling of examinations at high schools and colleges. Our goal is to schedule exams so that no student has two exams at the same time. There are some practical considerations, such as sections of a course having a common final exam. Graph-coloring models have proved to be valuable in practice here. Typically one might set in advance the number of time slots one wants to achieve and see if one can find a coloring of the conflict graph with this number of colors. If no solution exists, one might try to find a coloring that minimizes the number of conflicts, in some precisely definable sense.

Other examples of the way that coloring the vertices of a graph can be used to schedule or resolve conflict are:

a. Scheduling the use of tracks by railroads