[Computational Complexity] 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
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.
- AK, AL, AR, CT, DE, HI, IL, ME, MI, MN, MT, NE, NM, NV, SC, VA, WA
- AZ, DC, FL, KS, KY, MS, NC, ND, OR, PA, RI, TX, VT, WI, WY
- CA, CO, GA, ID, IN, LA, MA, MO, NJ, SD, WV
- IA, MD, NH, NY, OH, OK, TN, UT
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