Colorful Mathematics: Part I

3. Face colorings

The idea of a coloring of the faces of a map is to assign each face of the graph a color in such a way that two faces that share an edge must get different colors. Faces that meet only at a vertex are allowed to be colored the same color. In addition to general colorings of a map, mathematicians are interested in colorings that use the minimum number of colors. The (face) chromatic number of a map is the smallest number of colors that can be used to color the map subject to our rule, that faces with an edge in common get different colors. The map below has been colored with 4 colors. Note that the red of the red rectangle should be thought of as going off to infinity. Only a small part of the infinite face will be shown and colored.

 

Although the map above has been colored with 4 colors, this is not the face chromatic number for this map. You should show that this map can also be colored with 3 colors and even with 2 colors. Can you make a conjecture about when a map in the plane has face chromatic number 2?

The map below has been colored with three colors, but it can not be colored with 2 colors.


 

 

The face chromatic number of the map above is, therefore, 3. Now, can you find a map in the plane whose face chromatic number is 4? Can you find an infinite family of maps in the plane whose face chromatic number is 4?

In order to make progress on the four-color problem some "simplifications" were made in the question being addressed. An example of such a simplification is working with plane maps with nice properties rather than "any old" plane map. For example, it is not difficult to "reduce" the general question of coloring the faces of plane maps with four or fewer colors to the problem of coloring the faces of a 3-valent plane map with four or fewer colors, as follows. Suppose G is a graph drawn in the plane for which every vertex has valence at least 3. Such a graph is shown in the diagram below:

 

We can now replace a vertex of valence i in this diagram with a face with i sides, bounded by 3-valent vertices as shown in the diagram below:
 

This construction results in a new plane graph which is 3-valent. If one can four-color the faces of this graph, then one can four-color the faces of the original graph by shrinking the faces shown in black down to a single vertex. Remember that faces that touch at a vertex, after the shrinking process, but do not share an edge, can be colored the same color.

Some plane graphs have vertices of valence 1 or valence 2. One can also transform such graphs to new ones where the vertices of valence 1 and 2 are eliminated (this is done by creating faces with 1 side or 2 sides), and where the new "graph" (strictly speaking a multigraph) is plane and has only 3-valent vertices. Again, the original graph can be colored with four or fewer colors when the new one can. Thus, we can reduce the problem of coloring plane graphs with four or fewer colors to the problem of coloring plane 3-valent graphs with four or fewer colors. Mathematicians have been trained to take complex environments and transform them into new environments which are simpler or more highly structured. The hope is that it may be possible to make progress by getting a "handle" on a problem, thereby solving it after the transformation. If one is successful in this approach, one should not neglect to see if there are other interesting phenomena to be gleaned about the original situation after one has obtained the insight from the transformed one.

1. Introduction
2. Basic ideas
3. Face colorings
4. Vertex colorings
5. Some history
6. References