Feature Column from the AMS

Colorful Mathematics: Part I

4. Vertex Colorings

I have been treating the four-color problem using plane graphs. However, there is another perspective about the four-color problem. This involves the concept of the (geometric) dual of a map which has been drawn in the plane. The idea is illustrated in the diagram below, where the vertices all have valence 3. For each face of the original map one puts a blue dot in the face. One joins two of these blue dots with a blue line segment if the faces which contain the dots share an edge in the original graph.

Figure 2

Under this transformation, a plane graph is transformed to another plane graph, called the dual of the original graph. For each face with i sides in the original graph there will be an i-valent vertex in the dual graph. For each j-valent vertex in the original graph there will be a face with j sides in the dual graph. The number of edges in a graph and its dual graph are the same. (Some complications arise when one takes the duals of graphs with 1-valent and 2-valent vertices in that one gets a multigraph, rather than a graph.) Instead of coloring the faces of the original graph, one can color the vertices of the dual graph, where the rule for coloring the vertices of a graph is: Two vertices are not allowed to get the same color if they are joined by an edge. Note that when the original graph has only 3-valent vertices, the dual graph has faces which are all 3-sided (3-gon or triangles).

Nearly all recent discussions about the four-color problem treat it as a problem about coloring the vertices of plane graphs rather than coloring the faces of plane graphs. The statement of the problem now becomes the vertices of a plane graph can be colored with four or fewer colors. The reason that working in the vertex-coloring environment is appealing is that whereas one can only color the faces of a plane graph, one can color the vertices of any graph. This means that there is the hope one can prove a theorem about the coloring of plane graphs as a special case of a more general theorem which one proves about coloring any graph, plane or not. It may seem paradoxical that proving result X that includes Y as a special case is easier than proving Y directly, but this happens very often in mathematics: Abstraction and generalization pay!

To illustrate an attempt of this kind, the Swiss geometer Hugo Hadwiger (1908-1981) suggested a coloring problem that is still open today, which has the vertex-coloring version of the four-color problem as a special case. Ideas related to this are among the hottest and most fertile in graph theory and combinatorics. To get a perspective on Hadwiger's conjecture we need to discuss a few additional ideas. First of all consider the graph below:

Graph with a clique subgraph consisting of 5 vertices

Figure 3

This graph has a subgraph consisting of 5 vertices each joined to the other 4 vertices . A graph which has k vertices, each joined to all the others is known as a complete graph with k vertices, and is denoted K_k. When a graph has a subgraph which is a complete graph, this subgraph is known as a clique. The graph above has a clique with 4 vertices which is not a subgraph of a clique with 5 vertices, and a clique with 5 vertices. (Note that cliques on 5 vertices contain cliques on 4 vertices. Sometimes the definition of clique requires that it be "maximal" with respect to not being contained in a larger complete graph.) Since the vertices in a clique are all joined to each other, the vertex chromatic number of a graph must be at least as large as the size of the largest clique in the graph. It is traditional to use the notation χ(G) for the vertex chromatic number of a graph, the minimum number of colors that can be used to color the vertices of a graph so that vertices joined by an edge get different colors and to use ω(G) to denote the size of the largest clique subgraph in a graph. As just explained:

The graph in Figure 3 has a five-vertex clique, so its vertex-coloring number is at least 5. It is easy to check that the vertex chromatic number of this graph is 5 by actually coloring all the vertices of the graph with five colors.

Hadwiger's conjecture states that a graph which is n-chromatic (i.e. the smallest number of colors that can be used to color its vertices is n) has a subgraph which can be transformed to K_n by a sequence of edge contractions. It can be shown that Hadwiger's conjecture is true for n = 4 and that for n = 5 the conjecture is equivalent to the four-color theorem. Thus, it is now known to be true for n = 5. Using the four-color theorem, Hadwiger's conjecture is also known to be true for n = 6. It is still an open problem for n greater than 6. There are some who still hope for a simple proof of the four-color theorem by finding a simple proof of Hadwiger's conjecture.