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 G with n colours is a graph homomorphism G \to K_n. The chromatic number \chi(G) of G is the smallest positive integer n such that G admits a colouring with n colours.

Note that if G has a loop, then it cannot admit a colouring with any number of colours. In the loopless case, a trivial upper bound is \chi(G) \leq \# V(G), since G is a subgraph of the complete graph on V(G).

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

Conjecture (Hedetniemi). Let G and H be graphs. Then

    \[\chi(G \times H) = \min(\chi(G), \chi(H)).\]

Remark. Note that \chi(G \times H) \leq \min(\chi(G), \chi(H)): if G \to K_n is a colouring, then the composition G \times H \to G \to K_n is a colouring of G \times H, and similarly for H. Thus, it remains to rule out \chi(G \times H) = n with \chi(G) > n and \chi(H) > n.

Example. The case where \chi(G \times H) \leq 2 is easy to check:

  • If \chi(G) > 1 and \chi(H) > 1, then both G and H have an edge, hence so does G \times H. Then \chi(G \times H) > 1.
  • If \chi(G) > 2 and \chi(H) > 2, then both G and H contain an odd cycle. If G has an n-cycle and H an m-cycle with n and m odd, then these give morphisms C_n \to G and C_m \to H. Wrapping around m (resp. n) times gives morphisms C_{mn} \to G, C_{mn} \to H, hence to the product: C_{mn} \to G \times H. Thus, G \times H does not admit a 2-colouring since C_{mn} doesn’t.

Thus, if \chi(G \times H) \leq 2, then \chi(G \times H) = \min(\chi(G), \chi(H)).

Leave a Reply

Your email address will not be published.