## [Computational Complexity] Four Coloring the United States

Expand Messages
• 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
Message 1 of 1 , May 3, 2006
• 0 Attachment
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 colors, probably because a simple greedy algorithm takes five colors.

Four coloring the US is not difficult. So I found a Map Maker utility that lets you coloring the states anyway you want. So 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.

--
Posted by Lance to Computational Complexity at 5/03/2006 08:41:00 AM

Your message has been successfully submitted and would be delivered to recipients shortly.