## Wednesday, May 03, 2006

### Four Coloring the United States

For a talk I wanted to show a map of the United States using four colors with the usual constraint that every pair of states that share a common border have different colors. The four-color theorem says that such a coloring must exist.
So I tried Googling to find such a picture of a four-colored United States but I couldn't find one. NASA states it as a challenge but doesn't give the solution. Most maps I found like this one

use five or more colors, probably because they use a simple greedy algorithm.

Four coloring the US is not difficult. I found a Map Maker utility that lets you color the states anyway you want. Here is my four coloring.

My independent sets:
1. AK, AL, AR, CT, DE, HI, IL, ME, MI, MN, MT, NE, NM, NV, SC, VA, WA
2. AZ, DC, FL, KS, KY, MS, NC, ND, OR, PA, RI, TX, VT, WI, WY
3. CA, CO, GA, ID, IN, LA, MA, MO, NJ, SD, WV
4. IA, MD, NH, NY, OH, OK, TN, UT
The United States cannot be three colored, just consider Nevada and its neighbors. When writing this post I Googled on "four-color theorem" and the first link was this page which features a four-colored United States. Well at least I got a weblog post from all this work.

1. Did you have to use red and blue? Geez. Cool post, but I'm still instinctively turned off by red and blue maps of the US.

2. Wikipedia has a nice four-color map of the US.

3. It is customary not to count the surrounding region as needing a color. By the 4-color theorem if we don't require that Lake
Michigan have the same color as the Pacific/Atlantic coasts & Canadian/Mexican borders (and don't worry that some states look like lakes) then you should be able to reduce the color count in your diagram by one. Can you do that?

4. Are there any pair of states which must be the same color?

5. Since you are also coloring Hawaii, it seems to me that you should color the states that are adjacent to the boundary with 3 colors Otherwise the colorings of the connected components are not consistent with each other (i.e. you cannot extend the coloring to a coloring of the globe).

6. Every time we go to Z'Tejas (local Tex-Mex restaurant) my kids start four-coloring the map of the 48 contiguous states on the kids' paper placemats with the four crayon colors they hand out. As you say, it's not difficult as long as you work from one side to the other in a systematic order.

7. >Most maps I found like this one
>use five or more colors, probably
>because they use a simple greedy
>algorithm.

I think they just do it "by hand"

8. Is it known how hard it is to find a 4-coloring of a planar map?

9. Shown NP-complete by Stockmeyer in '73, says the first google hit to "4-coloring planar NP-complete".

10. Woops, that's to determine 3-colorability.

11. It's in TFNP, so it can't be NP-complete unless NP = coNP.

So the question is whether it is in P or possibly complete for a class like PPAD...

12. Note that the four-color theorem doesn't apply directly because of Michigan. :)

13. > Is it known how hard it is to find a 4-coloring of a planar map?

The Robertson, Sanders, Seymour, and Thomas proof leads to a O(n^2) algorithm.

14. So, uh, which ones voted for Kerry again?

15. Wikipedia's four colors are much nicer. Yours look like screen scrape from an old IBM PC in CMY color mode. :-)

Also, 4-colorability of a planar graph is in P and even in L and smaller complexity classes. :-) It is on a par with the sometimes-stated problem of factoring a prime number.

On the other hand, 4-coloring a planar graph is interesting and it's a neat result that it is O(n^2).

16. Actually, the 4-color theorem does not quite directly imply a 4-coloring of the 50 states because of the four corners.

On the other hand, the 50 states can be colored by the elementary result that a minimal graph that is not n-colorable has no vertex of degree less than n. The greedy algorithm works just fine, provided that the vertices are ordered in reverse according to their remaining valence.

17. There seems to be a curious degrees of freedom issue with different ways of coloring the USA map. The Getech web site allows the following pairs of states to interchange colors: Arizona/Utah, Washington/Oregon, South Dakota/Nebraska, Florida/Alabama, Vermont/New Hampshire or New Hampshire/Maine. But your map seems to only have New Hampshire/Maine as states that can be interchanged in their colors. What do you make of this? Am I just over looking possibilities? Do other USA four colored maps have other degrees of freedom?

18. You can find four coloring of several maps based on "spiral chains" including the ones for the USA map at

http://www.flickr.com/photos/49058045@N00/

Cahit