# 3-edge colorable cubic graph with an embedding on an orientable surface that is not 4-face colorable

Let $$G$$ be a simple cubic graph that is cellularly embedded on a surface such that the regions of $$G$$ are 4-colorable. Then by labeling the colors by the elements of $$\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}$$, we can 3-color the edges by taking the color of each edge to be the sum of its two adjacent regions.

The converse of this works for planar graphs - namely a 3-edge coloring can be converted into a face coloring. I would like to know an example where this fails for higher genus cubic graphs. Namely, is there an example of a cubic 3-edge colorable graph cellularly embedded of a surface that is not 4-region colorable?

• I think that for your first process to be correct, you also need the Graph $G$ to be bridgeless. This is the key point as you will never have an edge colored by (0,0) is $G$ is bridgeless, hence reducing to 3 colors. Otherwise this does not work. Jan 21, 2019 at 11:45
• @ThomasLesgourgues You're right - without reading too carefully, I assumed that this was one of the things implied by "cellular embedding" (when there's a bridge, the face that's on both sides of that bridge is kind of awkward) but it's not (apparently it's not awkward enough, according to Wikipedia.) Although maybe we might not consider a graph where a face borders itself to be $4$-colorable, or colorable at all. Jan 21, 2019 at 17:44
• @ThomasLesgourgues The condition that the regions of the graph on the surface are 4-colorable implies that we don't have anything like that going on. Jan 22, 2019 at 1:19
• @user101010. I think this is wrong, ANY planar graph is 4 face colorable, this is actually just the 4 color theorem. But you need the graph to be bridgeless in order to transfer the 4-face coloring into a 3-edge coloring. I might be wrong, happy to discuss Jan 22, 2019 at 9:30

Take a cellular embedding of $$K_5$$ in the torus, and turn it into a cubic graph by replacing each vertex by a $$4$$-cycle. Here's what this might look like: The result is $$3$$-edge-colorable: color the edges of each $$4$$-cycle using two of the colors, and use the third color on the long edges.
However, the faces of this embedding are not $$4$$-colorable. You can check that any two of the large faces of length $$8$$ are adjacent to each other (and therefore coloring all $$5$$ of these faces takes $$5$$ distinct colors).