Mathman Explains: Coloring of Maps

 

If you are following along with the Mathman Explains series, you might be really confused by how coloring maps connects to topology and graph theory.

If this is the first article that you're reading, you'll probably even more confused to how this is a researched problem in mathematics!

Don't worry, today we will go on a short adventure into the confusing world of map coloring, where we discover why coloring maps is secretly a complicated nightmare...

All you need to know is the little bit of graph theory that was covered in part 2 of this series!

When discussing the coloring of maps, we will mostly talk about the 4 Color Problem!

So, what is the 4 Color Problem?

Well, if given a map divided into sections, what is the minimum number of colors that you need to color the map in a way where the colors of two sections touching each other don't have the same color? While it is easy to just color every section of a map with a different color, finding the minimum amount of colors is much trickier. Before we get to the graph theory/topology side of the 4 Color theorem, let's see a solved example on an actual map!

 

Figure 1: 4 Color Mapping of the US

As we can see from figure 4, we can use only 4 colors to fill in the US map without any neighboring states having the same color. But are 4 colors the minimum number of colors? Maybe we can do 3? Let's see if Mathman can help us out!

As we can see, 4 colors is the minimum! But how coloring a map does this relate to graphs?

Well, we can actually represent a map as a graph, and then apply the 4 Color theorem to that graph!

Let's take Texas for example. Since we have lines that draw borders and those borders have to connect to each other at some point, we can represent Texas as a graph composed of vertices and edges in figure 2!

Figure 2: Conversion of the map of Texas to the Graph of Texas

The graph of Texas that we just created is actually a special type of graph called a planar graph. 

To state it simply, a planar graph is a type of graph where the edges don't cross. So, it pretty obvious that our graph representation of Texas is a planar graph! Here below in figure 3 is a nonplanar graph, where you can easily see that all of the inside edges of the graph cross in the middle:

Figure 3: Example of a nonplanar graph

As you can see from the nonplanar graph, the resulting graph is much more complex than a planar graph, and makes it more difficult to figure out which edges belong to each vertex. Because of the added complexity, the 4 color theorem might not work for nonplanar graphs. 

So, we've seen how the 4 Color Theorem works on maps, and now we know that these maps are planar graphs, so what does this look like with graphs?

Well, as we can see in figure 4 below, we have a map on the left with 5 regions labeled from A to E, much like how the regions on the US map are labeled by the name of the state. When we transform this map to a planar graph, we take the color of the region (for example region A is red) and color the corresponding vertex that color. So vertex A remains red, vertex B remains yellow, etc. So it's actually pretty simple!

Figure 4: 4 Color Theorem from maps to graphs

So, it turns out that the 4 Color Theorem is actually true for any arbitrary (randomly chosen) planar graph. Now that we discussed a proven theorem and what that might look like, I will end this short little blog by teasing what the Color Theorem looks like for objects that are not graphs. 

Remember Topology from part 1 of this series? Well we can apply the Color Theorem to topological structures as well! 

Figure 5: Color Theorem with topological structures

As we can see from figure 5, these topological structures that are in higher dimensions can also be colored with a different amount of minimum colors! 

There are so many more theorems and definitions that we could gush over, however we leave that as an exercise to the reader!