Wednesday, May 03, 2006

Four Coloring the United States



Five-Colored United States



Four-Colored United States

My independent sets:




  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

    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


  19. 1)
    2) "four-color theorem"
    3) Hit Return
    4) ???
    5) PrOfIT!1!