2
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Thomas Lesgourgues
    Jan 21, 2019 at 11:45
  • $\begingroup$ @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. $\endgroup$
    – Misha Lavrov
    Jan 21, 2019 at 17:44
  • $\begingroup$ @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. $\endgroup$
    – user101010
    Jan 22, 2019 at 1:19
  • $\begingroup$ @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 $\endgroup$
    – Thomas Lesgourgues
    Jan 22, 2019 at 9:30

1 Answer 1

Reset to default
3
$\begingroup$

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:

"cubification" of K5 embedded in a torus

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).

$\endgroup$
1
  • $\begingroup$ Thank you - this is perfect! $\endgroup$
    – user101010
    Jan 21, 2019 at 5:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .