# Graph colourings and Hedetniemi’s conjecture II: universal colouring

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.

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

To show this is a graph homomorphism, we must show that for adjacent we have . If two maps are adjacent, then for adjacent we have . Taking shows that , so

since is odd.

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