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

# Graph colourings and Hedetniemi’s conjecture I: statement of conjecture

The past three posts have been building up to the statement of the recently disproved Hedetniemi’s conjecture. I wanted to make an attempt to write about this, because from a first reading the main ideas of the counterexample seemed very familiar to an algebraic geometer. (More about this in a future post, hopefully.)

Definition. A colouring of a loopless graph with colours is a graph homomorphism . The chromatic number of is the smallest positive integer such that admits a colouring with colours.

Note that if has a loop, then it cannot admit a colouring with any number of colours. In the loopless case, a trivial upper bound is , since is a subgraph of the complete graph on .

Example. We have if and only if has no edges (we say that is discrete), and if and only if contains no odd cycles (we say that is bipartite). Indeed, if you try to produce a -colouring by colouring adjacent vertices opposite colours, either this produces a -colouring or you find an odd cycle.

Conjecture (Hedetniemi). Let and be graphs. Then

Remark. Note that : if is a colouring, then the composition is a colouring of , and similarly for . Thus, it remains to rule out with and .

Example. The case where is easy to check:

• If and , then both and have an edge, hence so does . Then .
• If and , then both and contain an odd cycle. If has an -cycle and an -cycle with and odd, then these give morphisms and . Wrapping around (resp. ) times gives morphisms , , hence to the product: . Thus, does not admit a -colouring since doesn’t.

Thus, if , then .

# Internal Hom in the category of graphs

In this earlier post, I described what products in the category of graphs look like. In my previous post, I gave some basic examples of internal Hom. Today we will combine these and describe the internal Hom in the category of graphs.

Definition. Let and be graphs. Then the graph has vertices , and an edge from to if and only if implies (where we allow as usual).

Lemma. If , , and are graphs, then there is a natural isomorphism

In other words, is the internal Hom in the symmetric monoidal category .

Proof. There is a bijection

So it suffices to show that is a graph homomorphism if and only if is. The condition that is a graph homomorphism means that for any , the functions have the property that implies . This is equivalent to for all and all . By the construction of the product graph , this is exactly the condition that is a graph homomorphism.

Because the symmetric monoidal structure on is given by the categorical product, it is customary to refer to the internal as the exponential graph .

Example 1. Let be the discrete graph on a set . Then is the complete graph with loops on the set . Indeed, the condition for two functions to be adjacent is vacuous since has no edges.

In particular, any function is a graph homomorphism. Under the adjunction above, this corresponds to the fact that any function is a graph homomorphism, since is a discrete graph.

Example 2. Conversely, is discrete as soon as has an edge, and complete with loops otherwise. Indeed, the condition

can only be satisfied if , and in that case is true for all and .

In particular, a function is a graph homomorphism if and only if either or has no edges. Under the adjunction above, this corresponds to the fact that a function is a graph homomorphism to if and only if has no edges, which means either or has no edges.

Example 3. Let be the discrete graph on a set with loops at every point. Then is the -fold power of . Indeed, the condition that two functions are adjacent is that for all , which means exactly that for each of the projections .

In particular, graph homomorphisms correspond to giving graph homomorphisms . Under the adjunction above, this corresponds to the fact that a graph homomorphism is the same thing as graph homomorphisms , since is the -fold disjoint union of .

Example 4. Let be the terminal graph consisting of a single point with a loop (note that we used instead for in this earlier post). The observation above that also works the other way around: . Then the adjunction gives

This is actually true in any symmetric monoidal category with internal hom and identity object . We conclude that a function is a graph homomorphism if and only if has a loop at . This is also immediately seen from the definition: has a loop at if and only if implies .

Example 5. Let and be the complete graphs on and vertices respectively. Then has as vertices all -tuples , and an edge from to if and only if when . For example, for we get an edge between and if and only if and .