Coloring Penrose Tiles

In 1976, mathematicians Kenneth Appel and Wolfgang Haken proved the four-color theorem: Four colors are sufficient to color any map so that regions sharing a common border receive different colors.

There are, however, special cases in which fewer than four colors suffice. For example, it takes only two colors to fill in a checkerboard pattern. In fact, any planar map in which intersecting lines run from edge to edge, requires only two colors.

Example of a map that requires only two colors.

Placing ceramic tiles so that adjacent tiles have different colors suggests similar issues. It is certainly possible, for example, to use just two colors when setting square tiles in a checkerboard pattern. Three colors are needed for a honeycomb pattern of hexagonal tiles.

One particularly intriguing case involves so-called Penrose tilings. In 1974, mathematical physicist Roger Penrose discovered a set of two tiles that, when used together, cover a surface without forming a regularly repeating pattern. One tile resembles an arrowhead and is described as a dart, and the other tile looks like a diamond with one foreshortened end and is known as a kite. The two pieces fit together to form a rhombus.

A portion of a kite-and-dart Penrose tiling of the plane.

It turns out there are many different pairs of quadrilateral shapes that form a aperiodic tiling pattern, though all are related in some way to the original kite-and-dart pair. One particularly striking set consists of a pair of diamond-shaped figures—one fat and one skinny.

A portion of a diamond-based (or rhomb-based) Penrose tiling of the plane.

Reports of attempts to color such Penrose diamond tilings led John H. Conway to conjecture that three colors suffice. In 1999, mathematicians Tom Sibley and Stan Wagon proved that to be the case. They described their results in the article "Rhombic Penrose Tilings Can be 3-Colored," published in the American Mathematical Monthly.

Sibley and Wagon generalized the result to any map (or tiling) made up of parallelograms, as long as two adjacent countries (or tiles) meet in a single point or along a complete edge of the constituent pieces. The mathematicians described such a map or pattern as "tidy."

Example of a three-colored Penrose diamond (or rhomb) tiling. 

The proof involved showing that, given a tidy finite map, a country has at most two neighbors. The results, however, do not hold for all possible quadrilateral shapes and configurations.

In 2001, Robert Babilon proved that tilings by kites and darts are three-colorable. Mark McClure than found an algorithm to three-color tilings by kites and darts and by rhombs.

Originally posted May 17, 1999