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.

    Torus, chromatic number 3
  • 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.

    Cayley graph

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

    Cayley Graph Coloring

    However, coloring with four colors exists, indeed one of the colors needs to be used only once.

    Coloring with four colors
  • 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.

    K4 on the projective plane
Difficulty level: Hard task
Reasoning task
Solution require uncommon idea
Cs translation
Send comment on task by email