Return to Answer

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.

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-set, a degree 1 regular subgraph spanning the vertices), then the complementary subgraph is a 2-set, i.e. a regular subgraph of degree 2 containing every vertex, homeomorphic to a union of circles, each component a cycle graph (I learned this terminology from this paper). If the 2-set is also bipartite (2-colorable, or every component has an even number of edges), then we may 2-color the 2-set and use a third color for the 1-set to get a Tait coloring of $G^*$. Then we can look for a 2-set $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-set with the above properties will be a bipartite 2-set, 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-set, and hence a 2-set), 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-set 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-set with essential odd cycles.

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.

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-set, a degree 1 regular subgraph spanning the vertices), then the complementary subgraph is a 2-set, i.e. a regular subgraph of degree 2 containing every vertex, homeomorphic to a union of circles, each component a cycle graph (I learned this terminology from this paper). If the 2-set is also bipartite (2-colorable, or every component has an even number of edges), then we may 2-color the 2-set and use a third color for the 1-set to get a Tait coloring of $G^*$. Then we can look for a 2-set $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 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-set with the above properties will be a bipartite 2-set, and hence the preimage graph will be 3-colorable (and a further 4-fold cover will give a 4-colorable dual triangulation).

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-set, a degree 1 regular subgraph spanning the vertices), then the complementary subgraph is a 2-set, i.e. a regular subgraph of degree 2 containing every vertex, homeomorphic to a union of circles, each component a cycle graph (I learned this terminology from this paper). If the 2-set is also bipartite (2-colorable, or every component has an even number of edges), then we may 2-color the 2-set and use a third color for the 1-set to get a Tait coloring of $G^*$. Then we can look for a 2-set $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-set with the above properties will be a bipartite 2-set, and hence the preimage graph will be 3-colorable (and a further 4-fold cover will give a 4-colorable dual triangulation).