Coloring planar tilings: four colors | Tangente

Despite their playful, even childish appearance, coloring problems in the plane pose formidable challenges for mathematicians and computer scientists. It took more than a hundred years to establish that any planar map divided into connected regions can be colored with four colors so that any two neighboring regions always receive different colors. This is the famous four-color theorem, first proposed in 1852. Its 1976 proof by Kenneth Appel and Wolfgang Haken required extensive computer processing and therefore failed to win general acceptance. A new, this time formal proof—though one that still relied crucially on computers—was published in 2005 by Georges Gonthier and Benjamin Werner; this proof is now far more widely accepted by the mathematical community. But although four colors suffice, they are by no means always necessary… Some maps can therefore be colored with three colors, or even just two.

Doing mathematics while stringing beads --------------------------------

Two colors can be enough to make an open necklace without any two beads of the same color touching. Simply alternate the colors… Now join the ends of this string of colored beads. To satisfy the constraint, the color at the beginning of the string must differ from the color at the end. The number of beads used must therefore be even. If the necklace contains an odd number of beads, a third color becomes necessary…

Now return to a map drawn in the plane, or to a tiling. As with a stained-glass window, two regions are considered neighbors if they share a boundary—a line that is not reduced to a single point.

There are essentially two kinds of tiling: regular tilings, made up of identical or isometric cells (quadrilaterals, hexagons, and so on), and irregular tilings, made up of non-isometric cells and sometimes containing gaps where cells do not meet. Three colors suffice to color regular tilings, and sometimes two. To color a regular hexagonal, or "honeycomb," tiling, simply stack alternating segments along ordered "rows" colored blue, green, and red. This tiling cannot be altered without introducing irregularities, unlike a plane tiled with quadrilaterals.

Within this tiling, isolate a cluster of cells arranged around a central element, the pivot, which is surrounded by a ring—bringing us back to our original necklace—consisting of an even number of cells (numbered 1 to 6), alternately green and blue. This cluster proves that three colors really are necessary.

These cells naturally give rise to a graph.

Representing a tiling as a graph has the advantage of showing which cells are adjacent without regard to their geometry. Each vertex of the graph represents a cell, together with its color, and each edge represents a boundary in the tiling. This representation ensures that the properties of the previous cluster—the pivot and its ring—apply to the entire regular tiling. Overlaying this cluster on all the other pivots in the tiling shows that the colors of the rings match up: the local features of the cluster containing the tiles numbered 0 to 6 extend across the entire plane.

In the original tiling, all the pivots are colored red. The green and blue cells form the rings, occupy the same clock-face positions, and also belong to neighboring clusters.

-

Say it with quadrilaterals -------------------------------

As with the honeycomb structure, quadrilaterals can be used to construct a regular tiling of the plane: simply stack alternating sequences of segments along ordered "rows" colored blue, green, and red, flipping or offsetting them. This tiling comes in two different arrangements.

The first case is identical to the hexagonal lattice: a ring of six tiles surrounds the pivot. This ring contains six cells—an even number—giving three different colors in all. In the second case, only two colors are needed. The ring does consist of eight cells, also an even number, but here the pivot can be assigned a color that satisfies the constraints.

When the elements of the plane are no longer isometric, the regular coloring scheme breaks down. To color the plane in the figure below, start by choosing a cluster of cells and its pivot. For example, the ring around cell 0 contains seven cells. Since this number is odd, four colors will be needed to color this first selection. Color pivot 0 red, then cells 1, 3, and 5 blue, alternating with green for cells 2, 4, and 6. But because cells 7 and 1 are neighbors, a new color—yellow—must be added to the palette to complete the coloring of this cluster.

To continue the coloring, select cells adjacent to the first cluster. For example, choose cell 1, which is blue, as the pivot of the new cluster. The cells belonging to the new ring are numbered 2, 0, and 7. To complete the ring, simply take the following cells, each of which touches the new blue pivot: 11, 12, 13, and 8 (to be colored red). This now complete ring contains an odd number of cells, so it will borrow a color—yellow—from the previous cluster.

But what if the map contains "holes," or gaps between regions? A missing cell in an irregular tiling is similar to the case of a two-color tiling. The ring continues beyond the missing connection. In the preceding diagram, this gap is represented by the uncolored cell 8. The following graph shows the consequences.

-

A gap in the tiling -------------------------

If cell 8 does not exist, there is a gap in the ring around pivot 2. The ring then consists of cells 1, 13, 9, 10, 15, 3, and 0.

If cell 8 is present, the ring bypasses cell 13 and connects through cells 1, 8, and 9. Cell 8 will be colored red to keep the color palette as small as possible. In any event, the four-color theorem guarantees that such a coloring is possible…