Colorful Mathematics: Part IV
2. Resolving conflicts (I)
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
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.
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.
The graph above has (vertex) chromatic number four but there is no coloring of the graph which uses each color twice. |
Welcome to the These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics. Search Feature Column Feature Column at a glance |