21-110: Conflict graphs

Map coloring and the four-color theorem

Pages 198–201 of Problem Solving Through Recreational Mathematics discuss the problem of coloring graphs and maps. The basic idea is to color the vertices of the graph (or the regions on the map) in such a way that adjacent vertices (or regions that share a border) are given different colors, and to do this with the fewest number of colors. (Note that, on a map, regions that meet only at a single point are not considered to share a border, and so Utah and New Mexico, for example, can be given the same color.)

The book states (in Theorem 6.8) that any planar map can be colored with at most four colors, which is a very famous theorem in mathematics called the four-color theorem. This fact was first proposed in 1852, though at that time it was only a conjecture, since it had not yet been proved. Over the next 124 years many mathematicians tried and failed to prove it. One attempted proof, given in 1879 by Alfred Kempe, was believed to be correct until Percy Heawood showed in 1890 that it was flawed; another proof, proposed in 1880, was shown to be incorrect in 1891. The first correct proof was given in 1976 by Kenneth Appel and Wolfgang Haken.

(It should be noted that this proof is incredibly lengthy, treating thousands of special cases one by one, and had to be generated by a computer. It sparked a great deal of controversy at the time, because it is so long that it is impossible for a single person to understand and verify it all. Since then the proof has been regenerated in several different ways, and simplified to some extent, but no one has yet been able to produce a proof that is simple enough and clear enough for any person to comprehend. For this reason there is still some doubt among some mathematicians about the correctness of Appel and Haken’s proof, though most mathematicians accept the proof as valid.)

The four-color theorem is of great importance to theoretical mathematics because the search for a proof provided a motivation for vast new areas of research, many of which are still being investigated today.

Applications of graph coloring

Despite its origins, the four-color theorem is not especially useful to mapmakers, for several reasons:

However, the idea of graph coloring in general, and the theorems that have been proved about it, are surprisingly useful in many different scenarios, some of which appear at first sight to have nothing to do with coloring.

For example, the game of Sudoku, played in a 9 × 9 grid, can be modeled by a graph having 81 vertices, one for each square, in which two vertices are joined by an edge if the corresponding squares are in the same column, the same row, or the same 3 × 3 block. Solving a Sudoku puzzle is equivalent to coloring this graph with 9 colors, representing the digits 1 through 9, in such a way that no two adjacent vertices are given the same color. (Why is this?)

As another (rather abstract) example, the ideas of graph coloring are used to decide how to efficiently allocate the memory available in the processor of a computer when programs are running.

The application we will be looking at here, though, is scheduling.

Scheduling using graph coloring

Imagine that the legislature of a certain state has five committees, whose members are as follows:

AgricultureEducationHealth and Human Services Natural ResourcesRevenue
Brown
Davis
Johnson
Miller
Williams
Anderson
Jones
Martinez
Smith
Williams
Martin
Moore
Smith
Thomas
Wilson
Brown
Jackson
Moore
Taylor
Thompson
Garcia
Harris
Johnson
Taylor
White

These committees would like to schedule weekly four-hour meeting times. Whenever a committee is meeting, the legislature as a body cannot meet, because some of its members will be busy in committee meetings. So, while it would be possible to schedule the five committees at five different times, this would consume 20 hours of the working week, and the legislature decides that it would be better to schedule the committees so that two or more of them are meeting at the same time whenever possible (in different rooms, of course). However, not all committees can meet at the same time, because some people are members of more than one committee; Williams, for example, is on both the Agriculture Committee and the Education Committee. What is the best way to schedule these five committees?

One way to tackle this problem is to model it with a graph. Let’s represent the committees with vertices. We’ll draw the vertices as open circles so that we can color them (we’ll see why in a bit).

Five vertices, representing the five committees

Now we need to represent the potential conflicts among the committees. A conflict exists if two committees share a member. So, for example, there is a conflict between the Agriculture Commitee and the Education Committee, since Williams is a member of both. On the other hand, there is no conflict between the Education committee and the Revenue Committee, because they have no members in common. We shall represent a conflict between two committees by drawing an edge between the corresponding vertices. The resulting graph is called a conflict graph. After identifying all of the conflicts among these five committees and drawing the appropriate edges, we get the following graph.

The conflict graph for these five committees

Next, let’s color the vertices of this graph, according to the rules of graph coloring: No two adjacent vertices can be given the same color, and we want to use as few colors as possible. We find that we can color this graph with three colors (black, white, and striped) as shown below.

The conflict graph, colored with three colors

How does this coloring give us a schedule for the committee meetings? We can interpret the three colors as representing different, non-overlapping four-hour blocks in which a committee can meet (for example, black can represent Monday 8:00–noon, white can represent Wednesday 1:00–5:00, and striped can represent Thursday 2:00–6:00). Since we have used only three colors, we need to have only three of these four-hour blocks. Then we schedule each committee to meet at the time corresponding to the color of its vertex. For example, using the times listed above, we could schedule these committees to meet at the following times:

AgricultureEducationHealth and Human Services Natural ResourcesRevenue
Monday 8:00–noon Wednesday 1:00–5:00 Monday 8:00–noon Thursday 2:00–6:00 Wednesday 1:00–5:00

In this way we have scheduled the committee meetings so that in all they take up only 12 hours a week. Of course, we could choose other four-hour blocks, as long as the blocks do not overlap.

Why does this method work? The key lies in the fact that the edges of the conflict graph represent all of the possible conflicts among the committees, and we have colored the vertices in such a way that adjacent vertices (representing committees that could potentially have a conflict) are given different colors (i.e., they are scheduled to meet at different times). The only committees that are scheduled to meet at the same time are those that have no members in common.

A simple algorithm for graph coloring

Here is a straightforward method that can be followed to color the vertices of a graph. (Note that it may not always produce a coloring with the least possible number of colors.)

  1. Associate colors with the positive integers 1, 2, 3, …. For example, perhaps 1 is red, 2 is blue, 3 is green, and so forth. Equivalently, you can just decide to “color” the vertices with numbers instead of colors. (The purpose of this step is to establish an “ordering” on the colors, so that we can meaningfully speak of the “first available color” in step 3.)
  2. Choose the uncolored vertex that is adjacent to the greatest number of colors. If there is a tie, break the tie by choosing the vertex that is adjacent to the greatest number of uncolored vertices. If there is still a tie, break the tie arbitrarily.
  3. Color the chosen vertex with the first color (that is, the color associated with the smallest integer) that is not already used for one of the neighbors of the chosen vertex.
  4. If not all of the vertices have been colored, return to step 2.

Things to watch out for

The four-color theorem is an important result, but it does not apply to graphs in general. It applies only to graphs that can be drawn on paper in such a way that none of the edges cross (such graphs are called planar graphs). A dual graph corresponding to the regions of a map, as described in Problem Solving Through Recreational Mathematics, is always a planar graph, so the four-color theorem applies. However, when coloring a conflict graph you may find that you need more than four colors.

For example, if every pair of committees in the example above had some member in common, then no two committees could be scheduled to meet at the same time, so five different meeting times would be necessary. The corresponding conflict graph would be a complete graph with five vertices. This graph cannot be drawn on paper without edges crossing, and it requires five colors if it is to be colored according to the graph coloring rules.

You should also be aware that the algorithm for graph coloring described above does not always use the least possible number of colors. Even if we know that a graph can be colored with, say, four colors, it is often necessary to backtrack to find such a coloring. For example, Martin Gardner published an article in the April 1975 issue of Scientific American as an April Fools’ joke, in which he claimed that the following map had been shown to require five colors:

Martin Gardner’s map that purportedly cannot be colored with fewer than five colors

Of course, we know (from the four-color theorem) that this planar map can be colored with just four colors, but finding such a coloring is difficult. Can you do it?

There is no known method that is reasonably quick, works for all graphs, and always uses the fewest possible colors. (It is believed that no such method exists.) From this point of view, the algorithm described above is about as good as any other. It might not always be perfect, but often it’s good enough.

Problems

  1. Ten friends have several interests in common, as shown in the table below.

    BasketballClassic rockFilmPainting Political discussionWine tasting
    Andrew
    Leah
    Megan
    Tanya
    David
    Steve
    Whitney
    Andrew
    Eric
    Megan
    Sarah
    David
    Joe
    Sarah
    Whitney
    Joe
    Leah
    Steve
    Whitney
    Eric
    Megan
    Tanya

    They decide to get together regularly to enjoy their interests. There is an activity center they can rent by the hour that has many rooms (and a gym), but they must rent the whole center, so they would like to schedule as many interest groups at the same time as possible. Of course, they cannot schedule two groups at the same time if there is someone who wants to participate in both groups. Suppose that each interest group wants to meet for two hours each week.

    1. Draw the conflict graph for this situation.
    2. Color the vertices of the conflict graph according to the rules for graph coloring.
    3. How should the interest groups be scheduled? How many hours a week must the activity center be reserved in total?
  2. There are seven final exams to be scheduled at a small college; the exams are for accounting, calculus, geography, history, Latin, physics, and sociology. Clearly these exams must be scheduled so that no student has two exams at the same time. These are the pairs of courses that have students in common:

    What is the minimum number of final exam times required? How should the final exams be scheduled?


Back to the 21-110 page

Last updated 21 April 2010. Brian Kell <bkell@cmu.edu>