Map Coloring

Today's Activities

• Introduction
  Color a map so that neighboring divisions (e.g., states, countries) are assigned different colors. Our goal is to use as few colors as possible.

  Technicality: The same color may be used for states such as Arizona and Colorado that do not share a non-trivial boundary.

• The Four-Color Theorem
  (brief history)

  Technicality: This relies upon an assumption that each individual division is contiguous (e.g., United States is not a contiguous country).

• Trial-and-error
  We will start by playing around with a variety of maps. See how well you can do.

• Method to the madness?
  Try to develop your skills beyond the trial-and-error phase.

  • Can you develop an efficient strategy for coloring the map with two colors (when possible)?
  • Can you develop an efficient strategy for coloring the map with three colors (when possible)?
  • Can you develop an efficient strategy for coloring the map with four colors?
  • Can you develop an efficient strategy for coloring the map with five colors?

• What is optimal number of colors for a specific map?
  If your best solution relies upon k colors, is there an easy way to convince someone that fewer colors is impossible?

• Make your own puzzle
  Try to stump your friend.

• Graph Theory
  The maps can be directly modeled as a formal graph, with a vertex for each country and an edge between any two countries that share a boundary.

• Further Discussion of the Four-Color Theorem and its History
  

• Extra Credit
  Try map coloring on other surfaces. How many colors are necessary and sufficient for maps on a torus?

Online Resources

• Computer Science Unplugged

• MATHmaniaCS

• MEGA Mathematics

• History of Four-Color Theorem by Robin Thomas