Feature Column from the AMS

Colorful Mathematics: Part III

4. Breaking the rules

Some questions related to coloring for specialized goals have even strayed from the basic notation that objects that "meet" must get different colors. Sometimes stretching the usual rules can lead to unexpected dividends. For example, there are two specialized coloring theorems (discussed in this section) which are concerned with the coloring of plane graphs all of whose faces are triangles. Such plane graphs (with at least 4 vertices) are sometimes called maximal planar graphs because the addition of a single edge joining two previously unjoined vertices will result in a non-planar graph (i.e. a graph which can not be drawn in the plane so that edges meet only at vertices). Another name for this family of graphs is plane simplicial graphs or plane triangulations.

Given a plane graph all of whose faces are triangles, suppose that we attempt to color the edges with two colors, r and b, such that the edges of each triangle get colored with two r (for red) edges and one b (for blue) edge. If we think of the colors as somehow coding lengths, we are finding a way of "combinatorially" having "congruent" isosceles triangles, because each triangle will have two sides of one length and the third side of a different length. This brings us to the first specialized coloring theorem (the second, Schnyder's Theorem, is near the end of the column).

Theorem:

Every maximal planar graph has a combinatorially isosceles coloring.

The key to proving this result is a theorem of Julius Petersen that any 3-valent graph that has no bridge has a disjoint collection of edges that include all the vertices (i.e. a perfect matching). The figure below shows a plane graph all of whose faces are triangles. Below it is a way of coloring the edges of that graph with two colors so that each triangle gets one blue edge and two red edges.

The previous graph with an isosceles triangle coloring of its edges

In the diagram above one can interpret the two colors as being edges of different lengths when one attempts to make a convex 3-dimensional polyhedron all of whose faces are congruent isosceles triangles. However, not surprisingly, there are combinatorial types of plane triangulations T for which there is no geometric realization of any combinatorially isosceles coloring of T by a convex 3-dimensional polyhedron where all the triangles are congruent isosceles triangles. Remember that for a given triangulation T there may be many congruent isosceles triangle colorings for T, some of which may be realizable by a polyhedron and some of which may not. An interesting open question growing out of this investigation is the following:

Does every combinatorial type of convex 3-dimensional polyhedron with only triangular faces admit a realization with isosceles triangle faces? (For this question the triangles do not all have to be congruent to one another, only isosceles triangles with different side lengths are required. It is also of interest if one can do this with strictly isosceles triangles, that is, when no triangle is equilateral.)

Another exciting kind of coloring for a plane triangulation is due to Walter Schnyder, who used it to get a deep insight into the usefulness of partial orders in understanding combinatorial phenomena. In order to understand what Schnyder accomplished, here is a moderately long excursion into the theory of partially ordered sets. Intuitively, a partial order is a collection of objects where one can say that some of the objects are related to each other but where other objects may be "incomparable" to each other. Thus, the ordering may not be "total" but only "partial."

Imagine that you are buying an air conditioner (A.C.). You are concerned with the price you pay, cheaper being better than more expensive, other things being equal. However, sometimes other things are not equal. Thus, you are not only concerned with the cost of buying the A.C. but also the cost of paying the electric bill to run it. Suppose that A.C.'s sold in your area must be given a number that represents the typical monthly cost of operating the unit. Also, you are concerned with the weight of the A.C. because you are planning to remove it from the window at the end of each summer and store it for the rest of the year. Thus, Brand A may cost $275, have a "standard monthly cost" of $47 and a weight of 43 lbs., while Brand B costs of $380, a monthly cost of $44 and weighs 40 lbs. Finally, Brand C costs $390, has a monthly cost of $45 and weighs 42 lbs.

While nearly everyone might agree that it would make no sense to buy air conditioner C because on every one of the three issues B is superior, the situation comparing A and B is more complicated. While a cheap initial cost is better than a high one, a cheaper monthly cost is better than a higher one, and a lower weight is better than a higher weight. Thus, it is not straightforward to say which of A or B is better.

We can describe each A.C. using a triple of numbers, the first being the cost, the second the monthly cost, and the third the weight. Air conditioner A would be described by (275, 47, 43) while B would be described by (380, 44, 40). We will use x R y to mean that A.C. Brand x is clearly superior to Brand y, where x = (x₁, x₂, x₃) and y = (y₁, y₂, y₃). For relationship x R y to hold we need to have that x₁ < y₁, x₂ < y₂, and x₃ < y₃. In the example above, B R C but we can reach no conclusion with regard to either A and B, or A and C with respect to relation R.

We now generalize the A.C. example. Use R to represent a "relationship" defined on a set of objects, where R obeys:

1. a R a does not hold (irreflexive).

Examples of irreflexive relations for real numbers would be "less than" or "greater than."

2. a R b and b R c implies a R c (transitive).

Examples of transitive relations are "parallelism" for lines in the Euclidean plane, and "less than," "greater than," and "equality" for real numbers.

If Rules 1 and 2 hold for a relationship R, we say that R is a partial order. (Some authors define a partial order by requiring that R is reflexive (i.e. a R a always holds), transitive, and antisymmetric, which means that a R b and b R a can not both hold.) Rules 1 and 2 imply that one can not simultaneously have a R b and b R a. Furthermore, for a given pair of objects a and b, neither a R b nor b R a need hold.

We can associate a partial order with a labeled graph H in a way that constructs a labeled graph based on the graph H. Given H, let P(H) denote the set consisting of the vertices of H along with the edges of H. The incidence order for the graph H is defined by the following relation < on P(H): v < e holds when v is a vertex of H, e is an edge of H and v is an endpoint of the edge e. Here is an example:

A graph and a graph of its associated incidence order

The graph H on the left has five vertices labeled v, w, x, y, and z and five edges labeled e, f, g, h, and i. The incidence order P(H) associated with H is shown on the right, with the vertices at the bottom and the edges at the top. A vertex is joined to those edges for which the vertex is an endpoint of that edge. Notice that the valences of the vertices of the original graph are reflected in the valences of the vertices in the bottom row of the graph on the right, while the valence of the vertices in the top row are all two. This reflects the fact that every edge has exactly two endpoints.

Not surprisingly, as noted above, graph P(G) associated with a graph reflects many of the properties of the original graph. Perhaps what is surprising is that using only this ordering information, one can tell whether or not a graph is planar. This is the content of an unexpected theorem of Walter Schnyder.

Theorem (Schnyder):

A graph is planar if and only if the dimension of P(G) is less than or equal to 3.

I need to provide a few more ideas to explain the dimension of a partial order. First, let me explain the idea of the coordinate order for n-tuples of real numbers. For simplicity, consider the case where we have ordered pairs (x, y) where x and y are real numbers. We will say that (s, t) ≤ (u, v) if s ≤ u and t ≤ v. The dimension of a partially ordered set Q is the minimum integer k, so that Q can be embedded in the space of k-tuples with the coordinate order. In practice, people work with an equivalent definition which is more combinatorial in nature but which would take us too far afield to describe. In addition to the result above, Schnyder also showed that if a graph has chromatic number at most 4, then the dimension of the graph (defined to be the dimension of the associated P(G)) is at most 4. This theorem suggests that Schnyder's work used ideas related to colorings of graphs. Here is the explicit connection.

Suppose we are given a plane triangulation with the infinite face of the triangulation labeled with v₁, v₂, and v₃ in clockwise order. Now we must assign one of the colors 1, 2, or 3 to each of the angles in the triangular faces of the triangulation other than the infinite face, where the following rules are obeyed:

a. Each angle at v₁ is colored 1, each angle at v₂ is colored 2, and each angle at v₃ is colored 3.

b. For each internal triangle the colors appear within the triangle in clockwise order.

c. At each internal vertex the colors can be read in a clockwise order as a non-empty string of 1's, followed by a non-empty string of 2's, followed by a non-empty string of 3's.

A coloring of a plane triangulation which obeys these rules is known as a Schnyder coloring. A triangulation and a Schnyder coloring of this triangulation are shown below:

A Schnyder coloring of the previous graph

Schnyder used what are now know as Schnyder colorings to prove his remarkable theorem about planar graphs. This result seems no less remarkable than those of Kuratowski and Wagner (mentioned in last month's column). In all three cases the topological question of whether a graph can be embedded in the plane is determined by combinatorial concepts. The lovely surprise, so common in mathematics, is that Schnyder colorings are the key to the original proof of Schnyder's theorems. However, Schnyder colorings have proved useful for problems other than the one they were originally used for. These problems concern the embedding of planar graphs in the plane, where the vertices of the graph are located at lattice points (i.e. points with integer coordinates) and the edges are straight line segments. Such embeddings are often known as grid embeddings. The goal is to find "efficient embeddings" of graphs with vertices at lattice points, where for example, efficiency is measured by the area of the clump of lattice points in which the graph winds up being embedded. It is possible that such embeddings may find application in computer chip design problems.

In the next installment of this treatment of coloring problems I will look at some of the applications of ideas about colorings to areas outside of mathematics.