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?
Best Answer
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).