Quadrangular faces
Task number: 4098
Find a graph that can be drawn on a torus so that all faces are bounded by a four-cycle and have the chromatic number three.
Hint
The graph can have an odd cycle as a subgraph, but not necessarily as a face.
Solution
For example, the toroidal grid \( 3 \times 3 \) contains a triangle, and it can be colored with three colors, see the picture.
Variant
Try to find a graph with the same drawing conditions, but to have the chromatic number four.
Hint
Try to start with the grid again, but this time wind it on the torus in a skewed way.
Algebraic tools, namely Cayley graphs , can be used to describe such a graph. Cayley graph for the group \( G \) and the set of generators \( X \subseteq G \) is a graph on \( | G | \) vertices \( V \), where each vertex corresponds to one element of the group \( G \) and the edges correspond to the composition with generators.
In other words, there is a bijection \( f: V \rightarrow G \) such that the vertices of \( u, v \) are joined by an edge, iff there is \( x \in X \) that \( f (u) x = f (v) \) or \( f (u) x^{-1} = f (v) \). The Cayley graph is usually denoted as \( Cay (G, X) \).
Examples: \( C_5 = Cay (\mathbb Z_5, \{1 \}) \), \( K_5 = Cay (\mathbb Z_5, \{1{,}2 \}) \).
Solution
Take the Cayley graph \( G = Cay (\mathbb Z_{13}, \{1{,}5 \}) \). This graph can be drawn on a torus with quadrangular faces.
It contains an odd cycle of 0-12, so its chromatic number is at least 3.
We show by a contradiction that the chromatic number is at least 4. If \( G \) could be colored with three colors, one of the colors would have to be used at least five times. Without loss of generality, let it be red and let 0 be red. Red cannot be used on its neighbors, so four of the remaining eight vertices must be red. On these vertices we can find an eight-cycle 2-3-4-9-10-11-6-7, so either red are 2,4,10 and 6; or 3,9,11 and 7. The first option is excluded due to the edge \( (2{,}10) \) the second due to \( (3{,}11) \).
However, coloring with four colors exists, indeed one of the colors needs to be used only once.
Variant
Can you find a graph that has a chromatic number four and whose drawing in the projective plane would have all the faces quadrangular?
Solution
Just cleverly draw the graph \( K_4 \). It has three faces, they are marked in color in the picture.
