Feature Column from the AMS

Colorful Mathematics: Part III

3. Exotic coloring problems

From its "humble" beginnings of addressing the number of colors needed to color a plane map, the theory of colorings has branched out in a staggering number of directions. We have already seen that in addition to coloring the faces of a plane graph, it is worthwhile to investigate the coloring of the vertices and the edges of any graph. Here is a sample of the many directions in which one can extend the theory of coloring.

Not all geographic maps fall under the coloring framework which we have looked at: A single country can have two separate parts (e.g., the former East and West Pakistan). If one wishes to adopt the rule that both parts of a single country should get the same color, we have a different problem from the four-color problem. Although Percy Heawood was unable to solve the four-color problem, he did give a complete solution to a special case of a nifty question of this kind. Using modern terminology, call a map drawn in the plane a k-pire map if there are "empires" each of which consists of exactly k disjoint faces. The coloring rule is that the faces which make up an empire get the same color while two empires which share an edge get different colors. Amazingly, Heawood answered some of the questions about empire graphs completely. For example, he produced a 24-faced 2-pire map which required 12 different colors, and proved that 12 colors are sufficient to color any 2-pire map. More generally he showed that a k-pire map can be colored with 6k colors. In 1984, nearly a hundred years after Heawood's first work on the problem, B. Jackson and G. Ringel showed that for any k > 1, there is a plane map of 6k mutually adjacent k-pires. Thus, the analogue of what Heawood showed for k = 2 is true in general. Note that the 4-color problem is the special case of the k-pire problem when k = 1.

G. Ringel (1959) developed a variant of this type of problem. Suppose that there are maps on two spheres, the earth and the moon. Each country consists of two connected pieces, one piece on the earth and one on the moon, where the color assigned to a country on the earth and moon is the same. What is the minimum number of colors need to color the maps so that countries that share an edge on either the earth or moon must get different colors? Ringel showed that the minimum number of colors is between 8 and 12, and in 1974 T. Sulanke showed that the value must lie between 9 and 12.

The plane graph below illustrates the concept of an entire coloring where each of the elements of the graph--the vertices, edges, and faces--has been assigned a color, so that adjacent elements get different colors. For an entire coloring, two faces that meet only at a vertex can get the same color, and a face and edge that meet only at a vertex can be colored the same color.

A 3-valent plane map whose vertices, faces, and edges have been seven colored

The 3-valent graph above has been successfully colored with 7 colors. It is conjectured that if G is a plane map with maximum valence Δ, then G has an entire coloring with (Δ + 4) colors. The theorem is known to be true for graphs of maximum valence 3. In 1996 O. Borodin showed the conjecture was true for maximum valence 7 or more and D. Sanders and Y. Zhao (2000), using a different approach (discharging), improved our knowledge by showing the result for graphs with maximal valence 6 or more. Thus, the only cases of the original conjecture that remain open are for plane graphs with maximal valence 4 or 5. Progress has also been made on the problem of total colorings of plane graphs where the goal is to color the vertices and edges of the graph.