The floret pentagonal tiling is shown below with two colorings. On the left is an optimal coloring: it uses the fewest colors possible, six, among colorings that respect all translational symmetries of the tiling. The quotient of the plane tiling by these symmetries is a tiling of the torus by six tiles, in which each tile touches each other, so six colors is optimal. But on the right, we have a periodic tiling with only three colors! The trick is that it has fewer symmetries: only 1/3 of the symmetries of the uncolored tiling preserve the colors in the coloring on the right.

two colorings of the floret pentagonal tiling

What can be said about this kind of problem more generally? If one has a periodic tiling of the plane, how few colors are required to color it periodically, and what can be said about the index of the coloring's symmetry group as a subgroup of the uncolored tiling's symmetries? The four-color theorem together with a standard application of König's lemma shows that any tiling has a four-coloring, but I don't see how to force the coloring to be periodic and still use only four colors in general.

ETA: Five colors suffice. Still unclear whether four colors are always possible.




Comments:

None: How is this different from coloring a graph on the torus?
2006-10-11T18:10:55Z

The subject says it all. If you have a periodic tiling of the plane, and you mod out by the periodicity, don't you always get a torus (one should check this statement - I vaguely remember it being true, but my memory is not reliable)? And if you have a map on the torus, can't you color it with seven colors?

Peter Shor

11011110: Re: How is this different from coloring a graph on the torus?
2006-10-11T20:32:52Z

Both of the colorings I show are colorings of a graph on a torus, but they are different tori: the left one is a torus tiled by six pentagons while the right one is a torus tiled by eighteen pentagons, a triple cover of the left torus.

My question can be rephrased as: if \( G \) is embedded on a torus \( T \), is there some \( k \)-tuple cover \( T' \) of \( T \) such that the lift of \( G \) to \( T' \) is 4-chromatic, and if so how small must \( k \) be?

None: Re: How is this different from coloring a graph on the torus?
2006-10-12T22:24:30Z

Thanks. Now I understand the question, I like it.

Peter Shor