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
we have
. If two maps
are adjacent, then for adjacent
we have
. Taking
shows that
, so
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).