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 .