Colorful Mathematics: Part IV

2. Resolving conflicts (I)

Imagine that a state legislature has nine committees that must meet every Thursday. Ideally, the committees meet in either of two special legislative hearing rooms. Sometimes scheduling a meeting in a room other than a special hearing room is also a possibility. Some of these committees have members in common, that is, there are people who serve on several different committees. Since people can not be in two places at once, it would be very desirable to have committees with common members meet at different times. The committee names are a, b, ..., h and the table below indicates with an X when a pair of committees has one or more people in common.

For example, committees a and d have a least one member in common. On the other hand, since there is no X in the c row and e column (or the e row and c column), these two committees have no member in common. Our first goal is to try to schedule these committees in as few time slots as possible. Furthermore, a solution that uses as few time slots as possible and requires the use of two or fewer special rooms at a given time would be ideal. To construct a mathematical model of this situation, we represent each committee by a dot (vertex) and join two committees by a line segment (edge) if the vertices that represent them correspond to committees that have an X in the cell corresponding to these committees in the table above. The result is the graph below:
 

 

Since two vertices in this graph are joined together with an edge if and only if the committees must meet at different times, the minimum number of time slots in which to schedule the committees can be found by computing the (vertex) chromatic number of this graph! (Chromatic numbers were defined in an earlier column.) Obviously, it is possible to color the vertices of the graph above with 8 colors because one can color each vertex with a different color. This is not the best answer. The coloring below uses 5 colors.
 

Figure 1

See if you can do better than 5 colors and try to find the chromatic number of the graph above by trial and error or by using one of the many graph-coloring algorithms that have been investigated. The theoretical news is not good, however. The problem of finding the vertex chromatic number for a graph is known to be an NP-complete problem. This means it is not likely that a "fast" (e.g. polynomial time in the number of vertices) algorithm will ever be found which computes the smallest number of colors needed to color the vertices of a given graph. However, since this graph is not very large, finding its chromatic number is not difficult. In this case re-drawing the graph above gives an insight:

 

 

This isomorphic drawing (i.e. a drawing with the same structure) of the graph in Figure 1 is a plane graph and, thus, by the four-color theorem its vertices can be colored with 4 or fewer colors. You should find a 4-coloring for yourself and label the vertices in a way which shows that it has the same structure as the original graph.

Below is shown yet another drawing of Figure 1, this time one which is not planar, but whose symmetry reveals information:

 

The four vertices a', d', f' and g' are each joined to the other three, showing that this graph has a clique (complete subgraph) of size 4, which means that the chromatic number must be at least 4. Since we saw the graph is indeed planar, there must be a four-coloring of the vertices. There are, in fact, many four-colorings of this graph. Unfortunately, the one above does not use each of the colors equally often. With greater care for this particular example we can achieve our second goal of not only finding a coloring using the chromatic number of colors but of using each color equally often! Thus, we have shown using an approach involving vertex-coloring that we can schedule the eight committees in four time slots where each committee meets in one of the special rooms.
 

In general, the chromatic number of a graph is not necessarily a factor of the number of vertices of the graph. Thus, it may not be possible to achieve a coloring with a minimal number of colors where each color is used equally often. Even when the chromatic number does divide the number of vertices of the graph being colored, one may not be able to achieve a coloring where each color is used equally often.
 

 

The graph above has (vertex) chromatic number four but there is no coloring of the graph which uses each color twice.

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