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 .