Periodic coloring of infinite planar graphs
The de Bruijn–Erdős theorem states that the number of colors needed to color an infinite graph is the same as the maximum number needed for its finite subgraphs. So for any reasonable definition of an infinite planar graph, the 4-color theorem for finite planar graphs implies that every infinite planar graph is also 4-colorable.
One way to construct infinite planar graphs is to make them periodic: start with any periodic tiling of the plane, decorate a single prototile by vertices and edges that may wrap from one tile to the next, and form an infinite graph from the copies of these decorations on all the tiles of the tiling. One possibility is to simply use one vertex in each tile, with edges that connect that vertex to its copies in each adjacent tile, in which case coloring the graph is the same as coloring the tiles of the tiling. For instance, here are two periodic colorings of the floret pentagonal tiling, one with the same translational symmetries as the whole tiling and six colors, and a second one that repeats with a fundamental domain that is 3x as large, but with only three colors.
However, the colorings given by the de Bruijn–Erdős theorem might not be periodic at all, even for a periodic graph generated in this way. And it might not always be possible to find a 4-coloring with the same period as the embedding: that would be the same as torus graph coloring, which can sometimes need as many as 7 colors, and the 6-coloring of the floret pentagonal tiling above is optimal for that period. However, thanks to a recent preprint and a 2020 MathOverflow posting with a 2025 answer both by user “Nate” we can now prove that periodic infinite planar graphs have periodic 4-colorings.
The preprint in question is “Three-edge-coloring (Tait coloring) cubic graphs on the torus: A proof of Grünbaum’s conjecture” by Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita, Bojan Mohar, and Tomohiro Sonobe, arXiv:2505.07002. Its characterization of cubic torus graphs without a 3-edge-coloring implies that every periodic planar cubic graph has a periodic 3-edge-coloring that at most doubles the fundamental domain. For finite planar graphs, cubic edge 3-coloring and vertex 4-coloring are equivalent, but in the periodic case there is another expansion by 2x in both lattice directions to go from edge coloring to 4-coloring. So the result ends up being that periodic planar graphs have 4-colorings with a fundamental domain (for their translational symmetries) that is at most 8x larger than that of the given graph.
This answers a question I asked on my blog 20 years ago (from which I copied the figure above). As I posted a few years later, periodic and aperiodic 3-coloring of periodic planar graphs can be different: there exist periodic infinite planar graphs that are 3-colorable, but for which all 3-colorings are aperiodic. The MathOverflow post on this was found by my student Cole Groen; thanks, Cole!