Map Coloring

This post first appeared at kkdegner@blog.com on 8/5/13.

This week I needed a map of all of the counties in Iowa for a little work I was doing in my office.  A quick Google search turned up quite a few options:

iowa-county-map

One of the first things I noticed about the maps was that the counties that were touching each other were each colored a different color.  This makes sense really, if all of the counties were the same color, there really wouldn’t be any point in coloring them at all, now would there?  Similarly if every other county was colored a different color (that is in the East/West direction), it might make it hard to differentiate between the counties that touch in the North/South direction.  So that leads me to the question; Why four colors for the map of Iowa’s counties?  Could it have been done with three colors?

The other thing I noticed about the maps was that if the counties shared a side, the colors were different, but if they shared a vertex (i.e. if they were diagonal from each other) this wasn’t necessarily the case.

Look in the top left corner of the map, for example.  I see a green to green vertex, a blue to blue vertex, yellow to yellow vertex, as well as an orange to orange vertex.  Being the purist that I am, I don’t really appreciate the fact that these colors are touching each other.  Which leads me to my next question . . . can I color the map of all of the counties in the state of Iowa only using four colors, such that all sides and all vertices don’t touch another county colored in the same way?

So, I set off to answer my questions with state of Iowa coloring pages and colored pencils:

picstitch

First, to tackle the problem of coloring the map using only three colors.

Twice, I got off to a promising start.  I used a technique that graph theorists call the Greedy Algorithm (Harris, et al, 2000).  That is, I used as few colors as possible until the third color was needed.  In other words, I was greedy with my colored pencils; not wanting to use more than I needed to when coloring the graph.  My use of the Greedy Algorithm and my coloring first horizontally and then vertically resulted in the following map colorings:

photomap     photomap3

In both cases, I ran in to trouble when one of the counties was bordered by more than four counties, see?

Then, I decided to try to tackle the second question which was “Can I color the map of all of the counties in the state of Iowa using only four colors, such that all sides and all vertices don’t touch another county colored in the same way?”  After a false start:

photomap2

I answered my question.  And the answer was yes!  (No, I’m not showing you my map.  Print off an Iowa map and start coloring.  You’ll get it, I promise!)

The colorings of the maps I’ve described are all proper colorings (Crommwell, 2000).  The Four Color Theorem tells us that only four colors are needed to properly color any map, but a natural question might be:

Are four colors always needed?  Can some maps be properly colored using only three colors?  Or two colors?

What do you think?  I think you’d better break out some colored pencils and get to work!

Advertisements