Four colors may not suffice, how about six?

The conjecture stated at the end of the unfinished 9th chapter of my Isometrica book states:

?Every periodic tiling is faithfully colorable in four or less colors?

Here “faithfully colorable” means that the periodic (crystallographic) tiling admits a “faithful” (to the tiling’s structure) coloring, that is a coloring that is both “maplike” (i.e., every two tiles sharing a border must be of different colors) and “perfect” (i.e., every isometry of the tiling must be color-consistent, mapping every two tiles of same color to two tiles of same color). [The connection with the famous Four Color Theorem is obvious: one only needs to worry about “maplike” there, but the ‘map’ can be arbitrarily complicated due to the lack of symmetries.]

I arrived at this conjecture in the summer of 2000, based on relatively simple coloring situations explored in my Symmetries classes at SUNY Oswego, on the isohedral tilings listed in Grünbaum and Shephard’s Tilings and Patterns (W. H. Freeman, 1986), etc (A tiling is isohedral when every two of its tiles are equivalent, that is mappable to each other by at least one of the tiling’s isometries.)

As recently as June 2014 I shared my conjecture with members of the Google Tiling Group, where Doris Schattschneider suggested that there might be k-isohedral counterexamples (with k > 1) — that is, non-isohedral tilings in which there exist k equivalence classes of tiles (under the equivalence relation defined in the previous paragraph).

At about the same time (summer 2014), David Bailey came up with a fascinating, if serendipitous, discovery: Herbert C. Moore (born Massachusetts US, 1863-c.1940), a salesman in the building business and an amateur inventor, was apparently an unknown pentagon tiling pioneer, and had patented on July 20, 1909, both what is nowadays known as the “Cairo tiling” and what I will call from here on “Moore’s tiling”; both tilings consist of congruent isosceles pentagons, but the former one is of p4g type (fourfold rotation plus (glide) reflection), whereas the latter is of p3m1 type (threefold rotation plus (glide) reflection). David is of course well known for his extensive Cairo tiling investigations, and he has now started exploring Moore’s tiling as well (more on this at the end of this post).

Moore’s tiling:


A few months later (fall 2014) I made my own discovery: Moore’s tiling provides a counterexample to my conjecture!


[The diagram above demonstrates the impossibility of a perfect maplike coloring in four colors for Moore’s tiling.]

A similar but much easier argument shows the impossibility of a perferct maplike coloring in five colors. But six colors do suffice, as the following two-part exhaustive and constructive approach (starting from the two possible ‘9-roots’ at center left) demonstrates:


[Note here that, out of the five 6-colorings obtained, the two middle ones are mathematically equivalent: indeed the color effects of their threefold rotations (taken clockwise) are (BRG)(OPY), (BGR)(OPY), (OPY) (upper coloring) and (OPY)(BRG), (OYP)(BRG), (BRG) (lower coloring), etc]


[Again, the first and third 6-colorings in the top row are mathematically equivalent; further, each 6-coloring obtained from the second 9-root (straight above) is equivalent to a 6-coloring obtained from the first 9-root (further above).]

It should be noted that out of the nine perfect maplike 6-colorings obtained only two are ‘regular’, that is they exhibit perfect balance among all six colors used; these two colorings are shown in full (with colors rearranged for ‘comparison’ purposes) right below:


These two slightly-different-looking colorings  are mathematically equivalent, as the color effects of their three types of threefold centers are exactly the same:


It is worth pointing out that Wieting’s The Mathematical Theory of Chromatic Plane Ornaments (Marcel Dekker, 1982), where only regular colorings are considered but the maplike property is not taken into account, predicts precisely four distinct perfect 6-colorings for the p3m1 type; ten years ago — in a desperate attempt to finish the said 9th chapter 🙂 — I had obtained three types of perfect, maplike 6-colorings employing two distinct tilings (shown right below), now I thought at first that Moore’s tiling provides the fourth one, but a closer look shows that the coloring exhibited above is equivalent to the colorings at the right:


[The coloring at the bottom right corner is new (April 2015) and shows how one p3m1 tiling provides three of four Wieting’s perfect 6-colorings; but it cannot apparently provide the elusive fourth one (at least not in maplike fashion)!]

The attentive reader may notice here that, just like Moore’s tiling, the two p3m1 tilings above do not admit perfect maplike colorings in four (or five) colors: I could therefore have disproved my conjecture already in the summer of 2005! Worse yet, the 1992 paper The classification of 2-isohedral tilings of the plane by Olaf Delgado, Daniel Huson, and Elizaveta Zamorzaeva (Geometriae Dedicata 42(1), pp. 43-117), provides several tilings requiring more than four, yet at most six, colors. In my defence, or even … in defence of Herbert C. Moore (who of course did not investigate coloring possibilities), I should point out that his 1909 p3m1 tiling is, unlike any tiling in the said paper, monohedral (i.e., all its tiles are congruent). (But Moore’s tiling is 3-isohedral — raising thus the question of a possible monohedral, 2-isohedral counterexample.) At any rate, Moore’s tiling could very well be the very first tiling conceived that is not perfectly 4-colorable!

Another noteworthy future of Moore’s tiling is that it is the only one of a host of Moore-like tilings (i.e., hexagonal tilings where each regular hexagon consists of three congruent pentagons) exhibited by David Bailey that requires six colors for a perfect maplike coloring. (But there are two pmg Moore-like tilings constructed by David that require five colors, the corresponding perfect maplike 5-colorings being non-regular.)


Tags: , , , , , , , , , , , , , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: