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.

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