Skip to Main Content

Colorful Mathematics: Part IV

Feature Column Archive

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

b. Assigning radio frequencies

When radio stations are geographically too close to each other and broadcast on the same or nearby frequencies they can interfere with each other. Draw a graph whose vertices are the stations and join them with an edge if they are are within a certain distance. Coloring the vertices of the graph where the colors correspond to frequencies gives an assignment where two stations with the same frequency will not interfere with each other.

c. Allocating resources

Suppose that there is a collection of basic tasks to perform which can be accomplished by allocating  resources. The time it takes to perform a task is a fixed constant amount. Furthermore, we have the list for each task Ti of resources Ri that need to be assigned to get the task done. We construct a graph as follows. For each task we create a vertex Ti and we join two tasks Ti and Tj by an edge whenever the lists Ri and Rj have at least one element in common. The reason for doing this is that we want to "tag" the fact that we can not do Ti and Tj at the same time because they need overlapping resource allocations. A coloring of the graph assures that tasks which get the same color can be performed simultaneously because the resources for them are simultaneously available. The shortest (total) time to get the tasks done will be accomplished when we have colored the vertices of the graph with the chromatic number of colors for the graph.

d. Organizing animals in zoos and pet stores

A pet store (zoo) wants to assign fish to aquaria (enclosures) so that fish (animals) that are not compatible (e.g. eat or attack each other) go into separate tanks (enclosures). For the pet store setting, if we create a vertex of a graph for each species of fish and join two vertices if the species they represent are compatible, then finding the chromatic number of the resulting graph will give the most "efficient" way to store the fish.

  1. Introduction
  2. Resolving conflicts (I)
  3. Resolving conficts (II)
  4. From schoolgirls to tournaments
  5. Mathematics and cell phones
  6. References