Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] Four Coloring the United States

Expand Messages
  • Lance
    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

      Five-Colored United States
      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.

      Four-Colored United States
      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.