### Colouring a Graph

#### Posted by Tom Leinster

It had always seemed to me that category theory provided no useful perspective on graph theory. But yesterday I learned a small fact that caused me to slightly revise that opinion. It’s that colourings of graphs — which seem to be a major source of questions in graph theory — are simply homomorphisms into a complete graph.

I’ll explain this, and I’ll describe a conjecture that Tom Hirschowitz told me about yesterday: for graphs $G$ and $H$,

The chromatic number of $G \times H$ is the minimum of the chromatic numbers of $G$ and $H$.

It’s amazing that something so basic is unknown!

For this post, a **graph** is a finite set equipped with a symmetric, irreflexive binary relation. The elements of the finite set $V$ are called the “vertices”, the relation is usually called $E$, and rather than saying that two vertices are related, we say that there is an “edge” between them. Concretely, then, “graph” means a finite undirected graph without loops (that being the “irreflexive” part) or multiple edges.

For instance, for each natural number $n$, the **complete graph** $K_n$ has vertex-set $\{1, \ldots, n\}$ and an edge between $i$ and $j$ whenever $i \neq j$.

A **homomorphism** of graphs is what you’d imagine. That is, given graphs $G = (V, E)$ and $G' = (V', E')$, a homomorphism $G \to G'$ is a map of sets $f\colon V \to V'$ such that for $x, y
\in V$,

$(x, y) \in E \implies (f(x), f(y)) \in E'.$

This gives us a category of graphs.

Graph theorists know a lot about colourings. By definition, a **colouring** of a graph $G$ by $n$ colours, or an **$n$-colouring** of $G$ for short, is a way of painting each vertex one of $n$ colours in such a way that no two vertices of the same colour have an edge between them.

Here’s the small fact I learned yesterday (from Wikipedia):

A $n$-colouring of a graph $G$ is the same thing as a homomorphism $G \to K_n$.

Why? Well, writing $G = (V, E)$, a homomorphism $G \to K_n$ is a map of sets $f\colon V \to \{1, \ldots n\}$ such that if $x, y \in V$ have an edge between them then the vertices $f(x)$ and $f(y)$ of $K_n$ have an edge between them. But every pair $(i, j)$ of vertices of $K_n$ is joined
by an edge *except when $i = j$*. So a homomorphism $G \to K_n$ is a map of sets $f\colon V \to \{1, \ldots, n\}$ such that if $x$ and $y$ are joined by an edge then $f(x) \neq f(y)$. That’s exactly an $n$-colouring.

This fact makes it obvious that colouring is functorial: given a homomorphism $f\colon G \to H$, every $n$-colouring of $H$ gives rise to an $n$-colouring of $G$. (Simply compose the maps $G \to H \to K_n$.) Concretely, we paint each vertex $x$ of $G$ the same colour as $f(x)$.

Every graph can be $n$-coloured for sufficiently large $n$: just paint all the vertices different colours. The **chromatic number** $\chi(G)$ of $G$ is the smallest $n$ for which there exists an $n$-colouring of $G$.

The functoriality of colouring means that $\chi(G) \leq \chi(H)$ whenever there is a homomorphism $G \to H$. Categorically put, $\chi$ is a functor $\chi \colon Graph \to (\mathbb{N}, \leq).$

Here $(\mathbb{N}, \leq)$ is the poset $\mathbb{N}$ regarded as a category: it has one object for each natural number, there is one map $m \to n$ when $m \leq n$, and there are no maps $m \to n$ when $m \gt n$.

The very famous four-colour theorem states that the chromatic number of a planar graph is at most four. For a long time it was only a conjecture. But there’s another fundamental conjecture about chromatic numbers — perhaps even more fundamental, as it doesn’t refer to the geometric notion of planarity. Tom Hirschowitz mentioned it to me by email yesterday; he’d just heard it from Stéphan Thomassé. Here goes.

The category of graphs has binary products, defined in the expected way: given graphs $G = (V, E)$ and $H = (W, F)$, the vertex-set of $G \times H$ is $V \times W$, and there’s an edge between $(v, w)$ and $(v', w')$ if and only if there are an edge between $v$ and $v'$ and an edge between $w$ and $w'$. The projections $G \times H \to G$ and $G \times H \to H$ are what you’d expect.

Now, the fact that there are *any* homomorphisms $G \times H \to G$ implies that $\chi(G \times H) \leq \chi(G)$. The same goes for $H$. So:

$\chi(G \times H) \leq \min\{ \chi(G), \chi(H) \}$ for all graphs $G$ and $H$.

The conjecture is that this is an equality:

Conjecture (Hedetniemi, 1966)$\chi(G \times H) = \min \{ \chi(G), \chi(H)\}$ for all graphs $G$ and $H$.

It’s known to be true for various classes of $G$s and $H$s, and I guess people have had their computers check it in millions of special cases. As I only learned about it yesterday, I know almost nothing more — only what I’ve read on Wikipedia and this page by Stéphan Thomassé. But presumably a question this basic, open since 1966, has attracted a lot of attention.

Intuitively (as Wikipedia says) the meaning of the conjecture is that $G \times H$ has no sneakily economical colourings. In other words, if your aim is to colour $G \times H$ with as few colourings as possible, you can’t improve on the following strategy: *either* colour $G$ minimally and then declare the colour of $(x, y) \in G \times H$ to be the colour of $x \in G$, *or* do the same with the roles of $G$ and $H$ reversed.

Categorically, the conjecture can be expressed as follows:

Conjecture (Hedetniemi)The functor $\chi: Graph \to (\mathbb{N}, \leq)$ preserves binary products.

That’s just because binary products in the category $(\mathbb{N}, \leq)$ are minima.

### Postscript: Perturbing the definition

In what I wrote above, I tried to stick closely to what I understand to be graph theorists’ conventions, except of course that some things are phrased in categorical language. I don’t know nearly enough graph theory to challenge the wisdom of those conventions.

However, I can’t help wondering whether things would become cleaner if we allowed our graphs to have loops. Formally, a **graph-with-loops** is a finite set equipped with a symmetric binary relation. Thus, what we’re calling a “graph” is a special sort of graph-with-loops: it’s a
graph-with-loops with no loops! Formally, it’s a graph-with-loops in which the relation is irreflexive.

Homomorphisms of graphs-with-loops are defined just as for ordinary graphs, and products are described in the same way too. Thus, $Graph$ is a full subcategory of $Graph_\text{L}$, the category of graphs-with-loops, and the inclusion preserves binary products.

Why allow loops? The reasons are aesthetic.

First, the irreflexivity condition tastes strange on a category theorist’s tongue. We’re suspicious of negatives.

Second, the category of graphs has the strange feature of possessing binary products but not a terminal object. This is “fixed” (if you think it’s a problem) by passing to the category of graphs-with-loops, in which the terminal object is the graph consisting of a vertex and a single loop on it.

Third, there’s a general rule, discussed at the Café before (though I can’t find it now) and possibly due to Grothendieck:

A good category containing some bad objects is preferable to a bad category containing only good objects.

I’m not keen on the words “good” and “bad” in mathematics, but I understand the intent. For instance, the rule tells us to work with the category of schemes rather than the category of varieties. The category of varieties is “bad” in lacking certain colimits, for example; but from the traditional point of view, some schemes are “bad”. Similarly, it suggests that categories of smooth spaces are preferable to categories of manifolds.

In our present situation, the presence of loops might be thought to make a graph “bad”, but allowing such graphs makes the category good.

One way in which a graph containing loops is “bad” is that it has no colourings at all. If a vertex $x$ has a loop on it, then there’s an edge between $x$ and $x$, so there’s no colour you can give it. Thus, the chromatic number of a graph containing one or more loops should be taken to be $\infty$. Chromatic number therefore defines a functor

$\chi\colon Graph_\text{L} \to \mathbb{N} \cup \{\infty\}.$

The category $\mathbb{N} \cup \{\infty\}$ is also “better” than $\mathbb{N}$: unlike $\mathbb{N}$, it has a terminal object (greatest element), $\infty$. Since $1$, the terminal graph-with-loops, contains a loop, we have $\chi(1) = \infty$. That is, $\chi$ preserves terminal objects. So it preserves binary products if and only if it preserves all finite products.

Actually, there’s something funny going on. A loop in a graph $G$ is a homomorphism $1 \to G$. In categories of spaces, a map from the terminal object to a space $X$ is often called a **point** of $X$. So, loops are points. This means that the graphs without loops — the “good” graphs — are exactly the graphs without points! What’s funny is that in some categories of spaces, such as the category of locales, the nontrivial spaces with no points at all tend to be seen as rather exotic. (For example, there’s the locale of surjections $\mathbb{N} \to \mathbb{R}$, which is nontrivial but has no points.)

Hedetniemi’s conjecture is straightforward when $G$ or $H$ contains a loop. For if $G$ contains a loop then we have a homomorphism $1 \to G$, which induces another homomorphism

$H \cong 1 \times H \to G \times H.$

So $\chi(H) \leq \chi(G \times H)$. (Concretely, if $G$ contains a loop on a vertex $x$ then $\{x\} \times H \subseteq G \times H$ is an isomorphic copy of $H$ contained in $G \times H$.) But we also know that $\chi(G \times H) \leq \chi(H)$; so $\chi(G \times H) = \chi(H)$. Since $\chi(G) = \infty$, this is exactly what Hedetniemi’s conjecture predicts.

So the conjecture can equivalently be reformulated as:

Conjecture (Hedetniemi)The functor $\chi\colon Graph_\text{L} \to \mathbb{N} \cup \{\infty\}$ preserves finite products.

At first glance this looks harder than the previous versions, since $Graph_\text{L}$ is a larger category and we’re asking for the preservation of terminal objects as well as binary products. But the observations above show that it’s actually equivalent.

Here’s a final question. The chromatic number functor is defined in terms of the complete graphs $K_n$. But what’s so special about the $K_n$s? What is their place within the category of graphs? I see no nice universal property that complete graphs satisfy. They look “indiscrete”, so at first I looked for some universal property similar to that satisfied by indiscrete topological spaces or indiscrete categories. But no — you have to be careful about the lack of loops. Perhaps the interplay of perspectives between $Graph$ and $Graph_\text{L}$ is somehow helpful here.

## Re: Colouring a Graph

I too find it a little perplexing that there has been little interaction between graph theory and category theory, so this is a welcome post.

Regarding “the” category of graphs: something that’s a little bit amusing is that if you forget about morphisms for a moment, then graphs as you defined them at the beginning (sets equipped with

irreflexivesymmetric relations) are sort of “the same thing” as sets withreflexivesymmetric relations, in the sense that there is a canonical bijection between such structures (they are in fact isomorphic as Joyal species). But they are very different of course from the viewpoint of structure-preserving functions! One thing that reflexive symmetric relations support and irreflexive symmetric relations do not is the process of contracting an edge to a point, which seems to be a prominent operation in at least some aspects of Graph Theory.I believe it is true that both the category of sets equipped with a symmetric relation, and the category of sets equipped with a reflexive symmetric relation, are quasitoposes (I’d have to double-check that). But the category of sets equipped with an irreflexive symmetric relation is not. This would sort of confirm the intuition that there’s something categorically “fishy” or not-good-smelling about the negative condition of irreflexivity.