Feature Column from the AMS

Colorful Mathematics: Part II

2. Insights into coloring planar graphs

Proofs of theorems about coloring problems in the plane, like the four-color problem, must use properties of the geometry/topology of the plane. One of the most fundamental results of this kind is a theorem of Camille Jordan (1838-1922), which seems so naive that many would argue that it needs no proof. Jordan showed that a simple closed curve in the plane (i.e. a flat closed loop of string) divides the points of the plane into exactly three sets: those points on the curve, the points inside the curve and the points outside the curve. The Jordan Curve Theorem is surprisingly hard to prove, precisely because it is so basic that one has to rely directly on properties of the plane itself, properties that distinguish the plane from other surfaces such as a torus (donut). It is somewhat easier to prove the polygonal version of the theorem which states that a simple closed polygon in the plane divides the points into three sets. To give you some flavor of the fact that the result is not as straightforward as you might think, take a convoluted polygon such as the one below, and try to tell quickly whether the blue point is inside the polygon or outside.

A convoluted plane polygon with a designated blue point

A knowledge of the Jordan Curve Theorem provides a way to tell easily, even for very convoluted polygons. Starting at a point clearly outside the polygon, draw a ray to the (blue) point that avoids the vertices of the polygon, as shown below.

A ray from the exterior to a blue point in a convoluted plane polygon

Since the ray above starts outside the polygon, and cuts three edges to reach the point, the point must be inside the polygon. This is because every time one moves across the boundary of the polygon, one goes from being outside the polygon to inside the polygon or vice versa. A ray which cuts the polygon an odd number of times has reached a point inside the polygon; a ray which cuts the polygon an even number of times has reached a point that is outside the polygon.

Based on the Jordan Curve Theorem one can prove a remarkable theorem, first observed by Leonhard Euler and first proved by Legendre. Stated in a form convenient for our purposes, Euler noted that if G is a map which results from a graph consisting of one piece drawn in the plane, the number of vertices V, faces F, and edges E of the map obeys:

V + F - E = 2

For example, for the map in Figure 1:

Plane graph whose faces are all triangles

Figure 1

we have V equals 5, F equals 6, and E equals 9, from which you can verify that V + F - E = 2.

From Euler's result, which is often referred to as the Euler Polyhedral Formula because Euler originally stated it for polyhedra (though he did not explicitly state what kind of polyhedra he had in mind, and the formula does not apply to all non-convex 3-dimensional polyhedra), one deduces that any graph drawn in the plane must have some face which has at most 5 sides. In fact, Alfred Kempe (1849-1922) knew this fact and gave a derivation of it based on Euler's Formula.

Using the fact that any plane map must have a face with five or fewer sides, one can show that any plane map can be colored with five or fewer colors. Until very recently this approach to the five-color theorem, due to Percy Heawood (1861-1955), has been the one used. Though the proof is moderately straightforward and not that difficult (it also requires the use of Kempe's work on Kempe chains) it involves a moderate amount of time and mathematical machinery to prove. The proof has become the one that every text uses. Thus, it was an interesting surprise when quite recently a new, easy, and more insightful proof of the five-color theorem was given. To understand what is involved we have to introduce some fascinating new ideas. In particular, although the original approach to coloring problems involved the coloring of regions of a map, it turns out that using the fact that plane graphs have duals, one can color the vertices of plane graphs instead. This has increasingly become the standard way of approaching coloring problems for plane graphs.

When we color the vertices of a graph (planar or not), it is usual to assume that the colors at our disposal are the same. However, an intriguing generalization of the idea of vertex-coloring has had many surprising ramifications. This approach was independently discovered by V.G. Vizing, and by P. Erdös, A. Rubin, and H. Taylor. The idea is that for each vertex one specifies a list of colors from which that vertex must be colored. A list-coloring of a graph is an assignment of a color to each vertex from the list of choices available at that vertex so that two vertices joined by an edge get different colors. A graph is called k-choosable if it is possible to list-color the graph where the list for each vertex has exactly k colors. The list-chromatic number of a graph H is the smallest possible k such that H is k-choosable, that is, the list-chromatic number specifies the smallest uniform size list that permits one to vertex-color the graph. Although they assumed that any plane graph could be vertex-colored with 4 colors, Vizing (1976), and Erdös, Rubin, and Taylor (1979), conjectured that the list-chromatic number of a plane graph was 5. In 1993 an example was discovered that showed that there are plane graphs which are not 4-choosable. In fact, examples were found that showed that graphs exist whose vertex chromatic number is 3 and which are not 4-choosable. Again, this meant that although one could color the graph's vertices with 3 colors, it is possible to find lists all with 4 colors so that the graph could not be colored properly from these lists. However, the landmark result in this area is due to the Danish mathematician Carsten Thomassen.

He verified the conjecture of Vizing (1975), Erdös, Rubin, and Taylor (1980).

Theorem (Thomassen):

Planar graphs are 5-choosable.

Thus, Thomassen provided a new proof of the Heawood theorem that plane graphs can be vertex-colored with five colors. Not only was the proof shorter than that of Heawood (though it proved something more powerful) but also it did not explicitly depend on the corollary of Euler's formula which stated that every plane graph had a vertex of valence 5 or less (a vertex with k edges is said to have valence k). The proof used mathematical induction in a very clever way as well as the Jordan Curve Theorem. Thomassen went on to prove additional remarkable results. For example, if G is a plane map whose smallest circuit has at least 5 sides, then G is 3-choosable. (The smallest length circuit in a graph is known as the girth ofthe graph. For a plane 3-valent graph G which is isomorphic to the graph of someconvex 3-dimensional polyhedron, there must be a face with the same number ofsides as G's girth.) Thus, for plane graphs which arise from convex 3-polytopes and whose faces have five or more sides, one can always produce a proper coloring of the graph from vertex lists all of size 3. (Lukasz Kowalik has examples which shows that if the plane graph does not arise from a 3-polytope but has faces with five or more sides then the graph may require 4 colors even though all the faces have 5 or more sides.)

The idea of a list-coloring takes a while to get used to. If one has a plane graph isomorphic to that of the regular dodecahedron (a plane 3-valent graph made up of 20 vertices and 12 5-gon faces) and one specifies the colors 1, 2, 3 for the first vertex, colors 4, 5, 6 for the second vertex, etc., then the coloring of the plane graph one gets is a coloring with 12 different colors, though each list has three colors. On the other hand, if one specifies the list 1, 2, 3 as the potential colors for every vertex, then Thomassen's Theorem concerning plane graphs of girth 5 means that one can find a vertex-coloring of the dodecahedron with 3 colors.

Ideas related to list-colorings have opened many new vistas concerning coloringof graphs in the plane and on surfaces such as the torus. List-colorings providea "textbook" example of how proving what appears to be a harder conjectureB because it is more general than a particular conjecture A, becomes, unexpectedly,easier to handle than the original problem.