I am taking graph theory this quarter, so my first instinct was to model this problem with a "graph". By graph, I mean a finite set of objects called vertices together with another set of edges consisting of unordered pairs of vertices. In my drawing, the small circles are the vertices, and the segments joining the circles are the edges. Two vertices are "adjacent" if they are joined by an edge.
I let each vertex represent a subregion. I joined two vertices by an edge if they shared a common side. Thus, no pair of adjacent vertices can be of the same color.

My graph will look as follows:

Vertex A is adjacent to vertices B and C because those are the subregions which share a side with the subregion A. Since A is adjacent to B and C, A must be a different color than B or C. However, B and C are not adjacent, so they can have the same color. In my picture, I chose A to be green, and B and C to be red. Now D is adjacent to B and C, so it has to be a different color than B or C. D is not adjacent to A, however, so D and A are allowed to have the same color. The same reasoning can be applied to the other vertices. As one can see from the above picture, it is possible to use only two differnet colors for this graph (with the rule that adjacent vertices must have different colors).
Now let's apply this information to the original circle picture. All we have to do is color in the subregions as they were colored in the above graph. The below picture shows the original picture colored in the same way as the above graph.

Extension of problem:

An extension of this problem is to allow for non-circular regions and non-straight "lines" (curved boundaries). An example of this is shown below.

Again, you can model this problem with a "graph". To make the graph, let vertices represent subregions. Join two vertices if the subregions represented by the vertices are adjacent (share a common curved side). Again, adjacent vertices must have different colors. For example, subregion 1 must be a different color from subregions 2, 3, 4, or 5. However, 1 can have the same color as 6 since 1 and 6 are not adjacent. See the below graph.

In this case, a minimum of 4 colors can be used. A colored picture is below.

Subregions 1 and 4 must be different colors (implying that at least 2 colors are needed).
Subregion 2 must be a different color from 1 or 4 (implying that at least 3 colors are needed).
Subregion 3 must be a different color from 1, 2, or 4 (implying that 4 colors are needed).
Subregion 6 can be the same color as 1.
Subregion 5 can be the same color as 3.


Remark: This region picture was taken from Applied Combinatorics
by Fred S. Roberts (Rutgers University)
1984 Prentice Hall, Englewood Cliffs, NJ

Return to Lori's EMT 725 Page