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