# A partial answer to my periodic tiling coloring question

A few weeks ago I asked whether periodic tilings of the plane have periodic colorings with four colors, and if so what the relation is between the periodicity of the coloring and of the tiling. As discussed in the comments there, another way of asking the same question is, if a graph is embedded in the torus, is there a finite cover of the torus such that the lift of the graph to the cover needs only four colors?

I still don't know the answer to the question for four colors, but the answer turns out to be yes for five colors. Albertson and Stromquist [PAMS 84:449-456, 1972] showed that if a torus graph has no noncontractable cycles of length less than eight, it's five-colorable. And it's easy to find a finite cover of a torus in which any noncontractable cycle has to pass across eight copies of the original torus, hence have length at least eight. Or, put another way, for any periodic tiling of the plane, if you make the pattern of repetitions big enough so that each tile in the tiling is eight or more tiles away from its nearest repeated copy, you can use only five colors in a periodic coloring.

I still don't know the answer to the question for four colors, but the answer turns out to be yes for five colors. Albertson and Stromquist [PAMS 84:449-456, 1972] showed that if a torus graph has no noncontractable cycles of length less than eight, it's five-colorable. And it's easy to find a finite cover of a torus in which any noncontractable cycle has to pass across eight copies of the original torus, hence have length at least eight. Or, put another way, for any periodic tiling of the plane, if you make the pattern of repetitions big enough so that each tile in the tiling is eight or more tiles away from its nearest repeated copy, you can use only five colors in a periodic coloring.