Four-face-colourings and three-edge-colourings

A four-face-colouring can be converted into a three-edge-colouring quite easily: 1. Assume the faces of G can be four-coloured with labels (0,1,2,3) 2. Label each edge of G according to \(i + j \;\textrm{mod}\; 3\) where i and j are the labels of the face adjacent to that edge. For each edge label there are two face label pairs that do not share any face labels. i,e the edge label \(0\) can come about either from faces \(0 + 3\) or \(1 + 2\).

Explicitly, the mapping from face labels to edge labels is:

\[\begin{aligned} 0 + 3 \;\mathrm{or}\; 1 + 2 &= 0 \;\mathrm{mod}\; 3,\\ 0 + 1 \;\mathrm{or}\; 2 + 3 &= 1 \;\mathrm{mod}\; 3,\\ 0 + 2 \;\mathrm{or}\;1 + 3 &= 2 \;\mathrm{mod}\; 3.\\ \end{aligned} \]

3. In a cubic planar G, a vertex v in G is always part of three faces and the colours of those faces determine the colours of the edges that connect to v. The three faces must take three distinct colours from the set \(\{0,1,2,3\}\).

4. From there, one can easily be convinced that those three distinct face colours can never produce repeated edge colours according to the \(i+j \;\mathrm{mod}\; 3\) rule.

This implies that all cubic planar graphs are three-edge-colourable. This does not apply to toroidal graphs. We have not yet generated a Voronoi lattices on the torus that is not three-edge-colourable. This suggests that Voronoi lattices may have additional structures that make them three-edge-colourable. Intuitively, it seems that the kinds of toroidal graphs that cannot be three-edge-coloured could never be generated by a Voronoi partition with more than a few seed points.