# Doubly periodic 4 color theorem?

Let $$G$$ be a graph embedded (without crossings) on a torus $$T$$. It's fairly well known that this implies the chromatic number of $$G$$ is at most 7. If I lift $$G$$ to the universal cover of $$T$$, we get a doubly periodic planar graph $$\tilde{G}$$ and of course the four color theorem tells us there is a four coloring of $$\tilde{G}$$.

With a little work I can improve this slightly to say that for any such $$G$$ there is a finite cover $$\widehat{T}$$ such that the corresponding cover $$\widehat{G}$$ is four colorable. My question is: Can this be done uniformly in $$G$$? If so, how small can we take the cover?

Concretely: Does there exist a covering map $$T' \to T$$ such the pull back to $$T'$$ of any graph embedded on $$T$$ can be properly four colored? Which covers work and what is the minimal degree of such a cover?

I was especially interested in the case where $$T = \mathbb{R}^2/\mathbb{Z}^2$$ and $$T'$$ was the 4-fold cover $$\mathbb{R}^2/(2\mathbb{Z})^2$$ but would be interested in hearing about any case.

EDIT: Since I thought this was a fun question I thought about it more and did some more searching through literature. Here are my current best partial results:

1) For a surface $$\Sigma$$ of genus $$g$$ there exists a degree $$36^g$$ cover such that any graph embedded on $$\Sigma$$ becomes $$6$$-colorable when pulled back to the cover.

2) For genus 1, any graph embedded on a torus becomes $$5$$-colorable when pulled back to the $$\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}$$ cover described above.

• Can you illustrate how you get your $\widehat{G}$? I'm almost certainly missing something, but if we take $G$ to be $K_7$, then I'm not sure what finite cover of $T$ four-colors $\widehat{G}$... – Steven Stadnicki Apr 29 at 0:01
• There is a pigeon hole principal argument - take your favorite essential curve missing the vertices of $G$ and take the infinite cyclic corresponding to this curve. It embeds in the plane and so has a 4-coloring. But the finite chunk of the graph in one of the lifts has only so many 4-colorings, so looking at the different lifts they eventually repeat. That repetition gives you a finite cover. Ian Agol observed this here. I would be interested in Nate's question for arbitrary genus also. – user101010 Apr 29 at 0:08
• Indeed, that pigeonhole argument sounds exactly like what I came up with. $K_7$ (at least the embedding I tried this afternoon, which might be unique?) was 4-colorable when lifted to the 4 coloring I mentioned above. – Nate Apr 29 at 1:21
• @Nate Apparently that embedding is in fact unique - Negami says that any 6-connected toroidal graph is uniquely embeddable in a torus. – user101010 Apr 29 at 1:32
• I thought a bit about the higher genus case. I believe I can at least show for any genus $g$ there exists a finite cover $\Sigma_h \to \Sigma_g$ such that the pull back of any graph on $\Sigma_g$ is $6$ colorable. Seems plausible such a cover could exist for 4 colors too. – Nate Apr 29 at 15:45

As Michael Klug points out in the comments, I've thought about related questions before. I'll make a few comments on the question.

Firstly, the usual reduction allows one to consider triangulations on a surface: if a graph $$G$$ does not induce a triangulation of $$\Sigma$$, then we can complete it to a triangulation $$G'$$ so that if $$G'$$ (or a cover $$\hat{G'}$$ induced by a cover $$\hat{\Sigma}$$) is 4-colorable then so is $$G$$ (or $$\hat{G}$$).

So let's assume that $$G$$ induces a triangulation of $$\Sigma$$. Then the dual graph $$G^*$$ (with respect to the embedding in $$\Sigma$$) is a cubic graph. If $$G^*$$ is 3 edge-colorable (i.e. has a Tait coloring), then one can see that a $$\mathbb{Z}/2\times \mathbb{Z}/2$$-cover $$\hat{\Sigma}\to \Sigma$$ will give a lift of $$G$$ which is 4-colorable. To prove this, identify the three colors with the non-zero elements of the Klein 4-group $$V=\mathbb{Z}/2\times \mathbb{Z}/2$$. Then coloring the vertices of $$G$$ corresponds to coloring the faces of $$G^* \subset \Sigma$$. If we color one face of $$G^*$$ by $$0\in V$$, then each time we cross an edge of $$G$$, we change the color by adding the element of $$V$$ corresponding to the edge coloring. This is locally well-defined near a vertex, but globally might have holonomy in $$V$$. So passing to a 4-fold cover $$\hat{\Sigma}\to \Sigma$$ induced by this holonomy, we get a pulled-back graph $$\hat{G}$$ which is 4-colorable. (In the planar case, there is no holonomy, and hence Tait's observation that Tait colorings suffice).

Thus it suffices to consider 3-edge colorings of cubic graphs in $$\Sigma$$. The Snark theorem implies that if the graph $$G^*$$ is not 3-edge colorable, then there is a Petersen minor (that is, a copy of the Petersen graph embedded topologically in $$G^*$$). The Petersen graph is non-planar, so must be embedded in an essential way in $$\Sigma$$ (not isotopic into a disk). Hence any Petersen subgraph of $$G^*$$ will not lift to some 2-fold cover of $$\Sigma$$. However, passing to a cover to which no Petersen subgraph lifts, there may be new Petersen subgraphs of $$\hat{G^*}$$ created. Nevertheless, one can ask if there is a finite cover $$\hat{\Sigma}\to \Sigma$$ such that the preimage of any embedded cubic graph in $$\Sigma$$ is not a Snark? Seems implausible, but it is a natural question to ask when thinking about virtual Tait coloring.

One can weaken the condition of Tait coloring, allowing passage to a finite-sheeted cover. If a cubic graph $$G^*$$ has a perfect matching (also called a 1-factor, a degree 1 regular subgraph spanning the vertices), then the complementary subgraph is a 2-factor, i.e. a regular subgraph of degree 2 containing every vertex, homeomorphic to a union of circles, each component a cycle graph . If the 2-factor is also bipartite (2-colorable, r every component has an even number of edges), then we may 2-color the 2-factor and use a third color for the 1-factor to get a Tait coloring of $$G^*$$. Then we can look for a 2-factor $$C\subset G^* \subset \Sigma$$ such that every non-bipartite component of $$C$$ is a non-trivial curve on $$\Sigma$$. In this case, we can pass to a $$2^{2g}$$-fold cover in which ever non-separating curve has each component of the preimage an even-index cover, and every separating essential curve has preimage components non-separating, and repeat, to get a finite cover for which the preimage of every essential curve is an even index cover on each component. Then the preimage of a 2-factor with the above properties will be a bipartite 2-factor, and hence the preimage graph will be 3-colorable (and a further 4-fold cover will give a 4-colorable dual triangulation).

One knows that every bridgeless cubic graph has a perfect matching (or 1-factor, and hence a 2-factor), known as Petersen's theorem. One could try to modify the proof to try to show that a graph $$G^*\subset \Sigma$$ has a 2-factor with odd cycles all essential. But I didn't see how to do this. In any case, it seems possibly easier to find a controlled cover of $$\Sigma$$ where the preimage of every cubic graph has a 2-factor with essential odd cycles.

Another special case is triangulations of even degree. Then we can try to 3-color the vertices. Once one 3-colors the vertices of a triangle, there is a unique way to continue the coloring, well-definied locally around a vertex because of the even degree hypothesis. This may have non-trivial holonomy, but passing to an $$S_3$$-cover (of index 6), we get a preimage which is a 3-colorable graph. This works e.g. for $$K_7\subset T^2$$.

Ultimately, this problem ought to be as hard as the 4-color theorem itself. Given a large graph embedded in a disk, one ought to be able to insert it into a disk on a surface $$\Sigma$$ of genus $$>0$$ as a subgraph. Coloring the graph larger graph in a finite-sheeted cover will induce a coloring of the planar graph. So I think one will likely have to use the 4-color theorem or parts of its proof as an essential ingredient in resolving this question.

One reduction I've contemplated is to make the surace the boundary of a handlebody, and pass to the universal cover of the handlebody. The preimage of the boundary is a planar surface, so the preimage of the graph $$\tilde{G}$$ is 4-colorable. The space of 4-colorings of $$\tilde{G}$$ is a closed subset of the Cantor set $$4^\tilde{V}$$, where $$\tilde{V}$$ is the vertex set of $$\tilde{G}$$. The covering translations form a rank $$g$$ free group. If there is a probability measure on the space of colorings which is invariant under the free group action, then I can show that there is a finite-sheeted cover (induced by a cover of the handlebody) which is 4-colorable, using a theorem of Lewis Bowen. However, I haven't been able to show the existence of such a probability measure (again, this may require non-trivial input from the proof of the 4-color theorem). One could do a similar thing with 2-factors of cubic graphs, where every contractible cycle is bipartite, and ask for an invariant probability measure on these. This approach, if it worked, would likely not give a uniform finite-sheeted cover.

• Thanks for detailed response! This is very similar to how I was thinking about the problem. – Nate May 1 at 17:05