Graph colourings and Hedetniemi’s conjecture II: universal colouring

Posted on by

In my previous post, I stated the recently disproved Hedetniemi’s conjecture on colourings of product graphs (see this post for my conventions on graphs). In the next few posts, I will explain some of the ideas of the proof from an algebraic geometer’s perspective.

Today we will start with the universal colouring on G \times \mathbf{Hom}(G, K_n).

Lemma. Let G be a graph. Then there exists an n-colouring \phi_{\operatorname{univ}} on G \times \mathbf{Hom}(G, K_n) such that for every graph H and every n-colouring \phi on G \times H, there is a unique morphism f \colon H \to \mathbf{Hom}(G, K_n) such that f^*\phi_{\operatorname{univ}} = \phi.

Proof. By this post, we have the adjunction

(1)   \[\operatorname{Hom}(G \times H, K_n) \cong \operatorname{Hom}(H, \mathbf{Hom}(G, K_n)).\]

In particular, the identity \mathbf{Hom}(G,K_n) \to \mathbf{Hom}(G,K_n) gives an n-colouring \phi_{\operatorname{univ}} \colon G \times \mathbf{Hom}(G, K_n) \to K_n under this adjunction. If H is any other graph, (1) gives a bijection between morphisms H \to \mathbf{Hom}(G, K_n) and n-colourings of G \times H, which by naturality of (1) is given by f \mapsto f^* \phi_{\operatorname{univ}} := \phi_{\operatorname{univ}} \circ (\operatorname{id}_G \times f). \qedsymbol

Corollary. To prove Hedetniemi’s conjecture, it suffices to treat the ‘universal’ case H = \mathbf{Hom}(G,K_n), for every n and every loopless graph G.

Proof. Suppose by contradiction that there is a counterexample (G,H), i.e. there are loopless graphs G and H such that

(2)   \[n = \chi(G \times H) < \min(\chi(G), \chi(H)).\]

Then there exists an n-colouring \phi \colon G \times H \to K_n, so the lemma gives a map f \colon H \to \mathbf{Hom}(G,K_n) such that \phi = f^*\phi_{\operatorname{univ}}. This forces \chi(H) \leq \chi(\mathbf{Hom}(G,K_n)) since an m-colouring on \mathbf{Hom}(G,K_n) induces an m-colouring on H by pullback. Thus, (2) implies

    \[\chi(G \times \mathbf{Hom}(G,K_n)) \leq n < \min(\chi(G),\chi(H)) \leq \min(\chi(G), \chi(\mathbf{Hom}(G,K_n))),\]

showing that (G,\mathbf{Hom}(G,K_n)) is a counterexample as well. \qedsymbol

Corollary. Hedetniemi’s conjecture is equivalent to the statement that for any loopless graph G and any n \in \mathbf Z_{>0}, either G or \mathbf{Hom}(G,K_n) admits an n-colouring. \qedsymbol

Example. By the final example of my previous post and the proof of the first corollary above, the cases n \leq 2 are trivially true. We can also check this by hand:

  • If G does not have a 1-colouring, then it has an edge. Then \mathbf{Hom}(G,K_1) has no edges by construction, since K_1 has no edges. See also Example 2 of this post.
  • If G does not have a 2-colouring, then it has an odd cycle C_m \subseteq G. We need to produce a 2-colouring on \mathbf{Hom}(G,K_2). Choose identifications V(K_2) \cong \mathbf Z/2 and V(C_m) \cong \mathbf Z/m with adjacencies \{i,i+1\}. Consider the map

        \begin{align*}\Sigma \colon \mathbf{Hom}(G,K_2) &\to K_2\\f &\mapsto \sum_{c \in C_m} f(c) \in \mathbf Z/2.\end{align*}

    To show this is a graph homomorphism, we must show that for adjacent f, g we have \Sigma(f) \neq \Sigma(g). If two maps f, g \colon G \to K_2 are adjacent, then for adjacent x, y \in G we have f(x) \neq g(y). Taking (x,y) = (c_i, c_{i+1}) shows that f(c_i) = g(c_{i+1}) + 1, so

        \[\Sigma(f) = \sum_{i = 1}^m f(c_i) = \sum_{i=1}^m \Big(g(c_{i+1}) + 1 \Big) = \Sigma(g) + 1 \in \mathbf Z/2,\]

    since m is odd. \qedsymbol

The case n = 3 is treated in [EZS85], which seems to be one of the first places where the internal Hom of graphs appears (in the specific setting of \mathbf{Hom}(-,K_n)).

References.

[EZS85] M. El-Zahar and N. Sauer, The chromatic number of the product of two 4-chromatic graphs is 4. Combinatorica 5.2, p. 121–126 (1985).

Leave a Reply

Your email address will not be published. Required fields are marked *