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.

  • 1
    $\begingroup$ 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}$... $\endgroup$ Apr 29 '20 at 0:01
  • 2
    $\begingroup$ 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. $\endgroup$
    – user101010
    Apr 29 '20 at 0:08
  • $\begingroup$ 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. $\endgroup$
    – Nate
    Apr 29 '20 at 1:21
  • 2
    $\begingroup$ @Nate Apparently that embedding is in fact unique - Negami says that any 6-connected toroidal graph is uniquely embeddable in a torus. $\endgroup$
    – user101010
    Apr 29 '20 at 1:32
  • $\begingroup$ 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. $\endgroup$
    – Nate
    Apr 29 '20 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.

  • 2
    $\begingroup$ Thanks for detailed response! This is very similar to how I was thinking about the problem. $\endgroup$
    – Nate
    May 1 '20 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.