### Graph Colouring and Cartesian Closed Categories

#### Posted by Tom Leinster

Just for fun, here’s a reformulation of a famous conjecture in terms of the cartesian closed structure on the category of graphs.

Hedetniemi’s conjecture says there’s no clever way of colouring a product of graphs. By “colouring”, I mean colouring the vertices in such a way that the ends of each edge get different colours.

Given graphs $X$ and $Y$, any colouring of $X$ gives rise to a colouring of $X \times Y$: just paint $(x, y)$ the same colour as $x$. Of course, the same is true with $X$ and $Y$ interchanged. Hedetniemi conjectured that if you want to colour $X \times Y$ with as few colours as possible, you can’t beat this method. That is, writing $\chi$ for the chromatic number of a graph — the smallest number of colours needed to colour it —

$\chi(X \times Y) = \min \{ \chi(X), \chi(Y) \}.$

This has been open since 1966.

I’ll explain how Hedetniemi’s conjecture is equivalent to the following statement about the cartesian closed category of graphs: for any graph $X$ and complete graph $K$, either $K^X$ or $K^{K^X}$ has a point.

For the purposes of this post, a **graph** $X$ is a finite set $V(X)$ with
a symmetric relation $E(X)$ on it, and a **homomorphism** is a map of
vertex-sets preserving the relation. Concretely, then, our graphs are
undirected and can’t have multiple edges, but each vertex may have a loop
on it (an edge from it to itself).

The category of graphs has finite products. They’re what you’d imagine: a vertex of $X \times Y$ is a pair $(x, y) \in V(X) \times V(Y)$, and vertices $(x, y)$ and $(x', y')$ are adjacent (that is, there’s an edge between them) if and only if $x$ is adjacent to $x'$ and $y$ is adjacent to $y'$.

The terminal graph $1$ consists of a single vertex with a loop on it. In
a category with a terminal object $1$, a **point** or global element of an
object $X$ is simply a map $1 \to X$. Here, then, a point of a graph $X$
is a loop in $X$.

Graph theorists most often like to consider “pointless graphs” — those without loops. But for what we’re doing here, it’s important to allow graphs to have points.

The category of graphs not only has finite products; it’s also cartesian closed. This means that for any graphs $Y$ and $Z$, there is another graph $Z^Y$ with the following property: for all graphs $X$, there is a natural one-to-one correspondence between homomorphisms

$X \to Z^Y$

and homomorphisms

$X \times Y \to Z.$

Here’s what $Z^Y$ looks like. A vertex is *not* a homomorphism from $Y$ to
$Z$, as you might guess; it’s *any* function $V(Y) \to V(Z)$. Two
functions $\theta, \theta': V(Y) \to V(Z)$ are adjacent in $Z^Y$ if and
only if

$(y, y') \,\,\text{ adjacent in }\,\, Y \implies (\theta(y), \theta'(y')) \,\,\text{ adjacent in }\,\, Z.$

In particular, $\theta: V(Y) \to V(Z)$ is adjacent to itself in $Z^Y$ (meaning that there is a loop on $\theta$) if and only if $\theta$ is a homomorphism $Y \to Z$. Differently put, the points of $Z^Y$ are exactly the homomorphisms $Y \to Z$. This is the special case $X = 1$ of the one-to-one correspondence just mentioned.

Now for colourings. As I wrote about once
before,
a (proper) colouring of a graph $X$ by $n$ colours is nothing more
than a homomorphism from $X$ to the complete graph $K_n$. By definition,
$K_n$ has $n$ vertices and an edge between each pair of *distinct*
vertices. It contains no loops, so it’s in some sense a maximal pointless
graph.

I want to draw your attention to a trivial but important point, which I’ll give a grand name so that I can refer to it later:

The Exclusivity PrincipleLet $X$ be a graph and $K$ a complete graph. Then $X$ and $K^X$ cannot both have points.

Why? Well, a point of $X$ is a homomorphism $1 \to X$, and a point of $K^X$ is a homomorphism $X \to K$, so if we have both then we can compose to get a point $1 \to K$ — and that’s impossible, as complete graphs are pointless. Like I said, trivial.

Another way to put this is that a graph with a point has no colourings. Concretely, this is simply the fact that if our graph contains a loop then we fall foul of the condition that different ends of each edge have to be different colours: they can’t be, because they’re the same vertex!

The **chromatic number** of a graph is the smallest number of colours you need to colour it:

$\chi(X) = \min \{ n : Hom(X, K_n) \neq \emptyset \} \in \mathbb{N} \cup \{\infty\}.$

A pointless graph can always be coloured by painting each vertex a different colour. On the other hand, we just saw that if a graph has any points at all, it has no colouring. So $\chi(X) \lt \infty$ if and only if $X$ is pointless.

Any graph homomorphism $W \to X$ induces a function $\Hom(X, K_n) \to \Hom(W, K_n)$ from the set of $n$-colourings of $X$ to those of $W$, by composition. In particular, if $X$ is $n$-colourable then so is $W$. Let’s write $W \leq X$ if there exists a homomorphism $W \to X$. Then

$W \leq X \implies \chi(W) \leq \chi(X).$

In particular, take graphs $X$ and $Y$. Since we have projections $X \times Y \to X$ and $X \times Y \to Y$,

$\chi(X \times Y) \leq \min \{ \chi(X), \chi(Y) \}.$

Conjecture (Hedetniemi, version 1)This is an equality.

In the case where $X$ or $Y$ has a point, it’s trivial. For suppose that $X$ has a point. Then we have a map $Y \cong 1 \times Y \to X \times Y$, as well as the projection $X \times Y \to Y$. This gives $Y \leq X \times Y \leq Y$, and so

$\chi(X \times Y) = \chi(Y) = \min \{\infty, \chi(Y)\} = \min \{\chi(X), \chi(Y)\}.$

So the substance of the conjecture is about pointless, or irreflexive, graphs.

To get to the rephrasing of the conjecture mentioned in the introduction, I want to move the focus away from the chromatic number $n$ and towards the family of complete graphs. So here’s a first, mild, rephrasing.

Conjecture (Hedetniemi, version 2)Let $X$ and $Y$ be graphs and $K$ a complete graph. If there is a homomorphism $X \times Y \to K$, then there is a homomorphism $X \to K$ or a homomorphism $Y \to K$.

Writing $K$ as $K_n$, this just says: if $\chi(X \times Y) \leq n$ then $\chi(X) \leq n$ or $\chi(Y) \leq n$. That is, if $\chi(X \times Y) \leq n$ then $\min\{\chi(X), \chi(Y)\} \leq n$. That is, $\min\{\chi(X), \chi(Y)\} \leq \chi(X \times Y)$. Since the converse inequality is trivial, that’s equivalent to version 1.

Now here’s a third, slightly different-looking, version of Hedetniemi’s
conjecture. I learned it from Godsil and Royle’s book *Algebraic Graph
Theory* (section 6.6).

Conjecture (Hedetniemi, version 3)For any graph $X$ and complete graph $K$, either $K^X$ or $K^{K^X}$ has a point.

The Exclusivity Principle implies that they can’t both have a point: so it’s a strict either/or.

Let’s prove that this is equivalent to version 2.

First suppose that version 3 is true. Take graphs $X$ and $Y$, and a complete graph $K$. We’ll prove the contrapositive of version 2: if there’s no homomorphism $X \to K$ and no homomorphism $Y \to K$ then there is no homomorphism $X \times Y \to K$. Supposing that there are no homomorphisms $X \to K$ or $Y \to K$, version 3 implies that there are homomorphisms $\alpha: K^X \to K$ and $\beta: K^Y \to K$. So we get homomorphisms

$K^{X \times Y} \cong (K^X)^Y \stackrel{\alpha^Y}{\longrightarrow} K^Y \stackrel{\beta}{\longrightarrow} K$

The composite is a homomorphism $K^{X \times Y} \to K$. So by the Exclusivity Principle applied to $K^{X \times Y}$, there’s no homomorphism $X \times Y \to K$.

Conversely, suppose that version 2 is true. Take a graph $X$ and a complete graph $K$. The cartesian closed structure gives us a counit homomorphism

$K^X \times X \to K,$

(which concretely is just $(\theta, x) \mapsto \theta(x)$). Version 2 then tells us that either there’s a homomorphism $K^X \to K$ or there’s a homomorphism $X \to K$. And that’s exactly what version 3 says.

So that’s the rephrasing of Hedetniemi’s conjecture. As I said, it’s just for fun: there’s no evidence that it leads anywhere.

You could also state a fourth version:

Conjecture (Hedetniemi, version 4)For any graph $X$ and complete graph $K$, at least one of the graphs $X, K^X, K^{K^X}, K^{K^{K^X}}, \ldots$ has a point.

But that seems like just a dressing-up of version 3. Why? Well, for any graph $A$, the cartesian closed structure gives us a unit map $\eta_A: A \to K^{K^A}$. Taking $A = X$ and $A = K^X$ in turn gives us maps

$K^{(\eta_X)}: K^{K^{K^X}} \to K^X, \qquad \eta_{K^X}: K^X \to K^{K^{K^X}}.$

(Category theorists will now mumble the words “triangle identity”.) So $K^X$ has a point iff $K^{K^{K^X}}$ does. More generally, by the same argument, the $n$th member of this sequence has a point iff the $(n + 2)$th member does, for $n \geq 2$. So we might as well truncate the sequence to

$X, K^X, K^{K^X}.$

We can also drop the $X$, since the unit map $\eta_X: X \to K^{K^X}$ tells us that if $X$ has a point then $K^{K^X}$ does too. So we’re back to version 3.

## Re: Graph Colouring and Cartesian Closed Categories

If you could use the ideas to help

provethe Hedetniemi conjecture, category theorists would be eternally grateful, since they’d have a nice answer to “what has category theory ever done for graph theory?”Of course you’ve already thought of this.