I was thinking again today about a question I asked some time ago, whether every periodic infinite planar graph (that is, a graph formed by unrolling a toroidal graph onto the universal cover of the torus) has a periodic 4-coloring (possibly with a larger fundamental domain).

It turns out to be known that there exist periodic infinite planar graphs that are 3-colorable, but for which all 3-colorings are aperiodic. Also, using the same construction, one can show that it's undecidable to determine whether a periodic infinite planar graph is 3-colorable. The reference is "\( k \)-sat on groups and undecidability", by Michael Freedman in STOC 1998.

So that's a hint that the 4-coloring question might be difficult...