Feature Column from the AMS

Colorful Mathematics: Part II

3. Edge-colorings

We have looked at various coloring problems of plane graphs where we colored either the faces or vertices of the graph. If we can color vertices and faces of a graph, why can't we color the edges of a graph? The answer, of course, is that we can. The usual rule for such a coloring is that an edge-coloring of a graph (planar or not) is an assignment of a label to each edge so that any two edges that share a vertex get different colors. Obviously, if the maximum valence of a graph is Δ, then the minimum number of colors to color the edges of the graph must be at least Δ. This number, the minimum number of colors to color the vertices of a graph H is called the chromatic index of a graph and is usually denoted by χ'(H). A remarkable theorem of the mathematician Vadim Vizing is that the chromatic index of any graph is Δ or Δ + 1. In particular, this is true of plane graphs. It is tempting to think that Vizing's Theorem should apply to multigraphs (no loops allowed) as well as to graphs. However, it turns out this is not true. This can be seen by trying to color the multigraph below:

This multigraph illustrates that a theorem of Claude Shannon (1916-2001), much better known for his work on information theory, gives the best possible upper bound. His theorem states that for a multigraph the chromatic index of a graph G is no more than 3Δ(G)/2 where Δ(G) denotes the maximal valence of any vertex in G.

You may be wondering if edge-colorings have any relation to the four-color problem. The remarkable answer is "yes." The connection comes because of the work of P. G. Tait (1831-1901) and Julius Petersen (1839-1910). Tait, in addition to his work on graph theory, was an early investigator of knots. Petersen, a Danish mathematician, did work on relating rule and compass constructions to the solution of algebraic equations.

Peter Tait and Julius Petersen

We have already discussed that the problem of coloring the faces of a plane graph can be reduced to coloring the faces of a 3-valent plane graph. The essence of what Tait observed is that the edges of a 3-valent plane graph, which contains no edge whose removal will increase the number of pieces of a graph (such an edge is known as a bridge), can be colored with 3 colors if and only if the faces of the graph can be colored with four or fewer colors. By way of an example, the graph of a 3-dimensional cube below has had its edges colored with three colors so that edges that meet at a vertex are colored differently.

Petersen showed that the non-planar graph below does not have a three-coloring of its edges. The Petersen graph is also remarkable in lacking a circuit which visits each vertex once and only once, a so-called Hamiltonian circuit. One of the many, very different looking possible drawings of the Petersen graph is shown below:

The connection between Hamiltonian circuits and coloring problems shows the way that questions evolve and take on a life of their own one. Given a connected graph, the notion of finding a tour of the vertices which is a simple closed curve and visits each vertex once and only once now has a name that honors the great Irish mathematician William Rowan Hamilton, though the problem had been raised earlier by the Reverend Thomas Kirkman (1806-1895). Hamilton raised the issue in conjunction with the question of whether the dodecahedron has a tour which visits each vertex once and only once. (Hamilton called this theIcosaian game, icosa referring to the 20 vertices of the dodecahedron.)