Skip to main content
MathOverflow

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

5
  • $\begingroup$ Dear Ian, Very nice question! if we start with an embedding of the complete graph like $K_6$ on $RP^2$ or $K_7$ on the torus can we find such a cover? $\endgroup$ Commented Sep 11, 2016 at 15:54
  • 1
    $\begingroup$ @GilKalai: The question is trivial for graphs in $\mathbb{RP}^2$, since a 2-fold cover will be planar. For $K_7$ on the torus, notice that it is a valence 6 triangulation. Thus, it is commensurable with a triangulation of the torus with 4 vertices which is 4 colorable (the 4-fold cover of the 1-vertex triangulation), and hence it has a 4-colorable cover. $\endgroup$ Commented Sep 11, 2016 at 17:12
  • $\begingroup$ "it is a valence 6 triangulation. Thus, it is commensurable with a triangulation of the torus with 4 vertices " Ian, I dont understand it but maybe I miss something basic. Does this argument extend to other $K_n$'s on surfaces of higher genus? $\endgroup$ Commented Sep 11, 2016 at 18:22
  • 1
    $\begingroup$ @GilKalai: It might extend some times. Regular triangulations of surfaces are all commensurable. So if a $K_n$ has an embedding as a triangulation in a surface, and one can find a regular triangulation of degree $n-1$ which is 4-colorable, then the $K_n$ embedding is virtually 4-colorable by commensurability. However, I'm not sure which $K_n$'s embed as regular triangulations on a surface. More generally, one could try to answer the question for regular cellulations of surfaces (where all faces and vertices have the same degree). $\endgroup$ Commented Sep 11, 2016 at 22:09
  • 5
    $\begingroup$ I can answer the question now for tori. Take a map on a torus (thought of as a cell structure), and a simple closed non-trivial curve in the 1-skeleton. Take the infinite cyclic cover dual to this curve (so cut along the curve to get an annulus, and glue infinitely many copies of this annulus end-to-end). Then the map on the infinite cyclic cover is 4-colorable, since it is planar. But there are only finitely many colorings of the annuli, and there must be two distinct curves which have the same adjacent colorings. Then cut and glue along these curves to obtain a compact 4-colored torus. $\endgroup$ Commented Sep 12, 2016 at 21:52