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.

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