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 .

**Lemma.** *Let be a graph. Then there exists an -colouring on such that for every graph and every -colouring on , there is a unique morphism such that .*

*Proof.* By this post, we have the adjunction

(1)

In particular, the identity gives an -colouring under this adjunction. If is any other graph, (1) gives a bijection between morphisms and -colourings of , which by naturality of (1) is given by .

**Corollary.** *To prove Hedetniemi’s conjecture, it suffices to treat the ‘universal’ case , for every and every loopless graph .*

*Proof.* Suppose by contradiction that there is a counterexample , i.e. there are loopless graphs and such that

(2)

Then there exists an -colouring , so the lemma gives a map such that . This forces since an -colouring on induces an -colouring on by pullback. Thus, (2) implies

showing that is a counterexample as well.

**Corollary.** *Hedetniemi’s conjecture is equivalent to the statement that for any loopless graph and any , either or admits an -colouring.*

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

- If does not have a -colouring, then it has an edge. Then has no edges by construction, since has no edges. See also Example 2 of this post.
- If does not have a -colouring, then it has an odd cycle . We need to produce a -colouring on . Choose identifications and with adjacencies . Consider the map

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

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