<p>Sure, category theorists know such things, but I think for the difficult results that graph theorists care about, the generalities of category theory may at best help as an organizing principle. This is a bit similar to the theory of combinatorial species, which is a way of doing combinatorics inspired by category theory.</p>

<p>Here are some other basic observations, you can read more about such things in Lawvere's <a href="https://github.com/mattearnshaw/lawvere/blob/master/pdfs/1989-qualitative-distinctions-between-some-toposes-of-generalized-graphs.pdf" rel="nofollow noreferrer">Qualitative distinctions between some toposes of generalized graphs</a>, Categories in computer science and logic (Boulder, CO, 1987), volume 92 of Contemporary Mathematics, 261–299. American Mathematical Society.</p>

<p>The category of directed graphs is a presheaf topos on the site consisting of two parallel arrows (so that a presheaf is given by two sets $E$ and $V$ and maps $t : E \to V$ and $s : E \to V$), see <a href="https://arxiv.org/abs/math/0306394" rel="nofollow noreferrer">A Guided Tour in the Topos of Graphs</a> by Sebastiano Vigna.</p>

<p>For any given $n$, the category of $n$-colored graphs is a topos, because it is just the slice of the topos of graphs over the complete graph on $n$ vertices (an $n$-coloring of $G$ is just a morphism $G \to K_n$).</p>

<p>As Lawvere explains, several other categories of graphs are toposes because they are (equivalent to) toposes of monoid actions for a suitably chosen $M$. Let's just do one. Consider the monoid $M$ of endomaps on $2 = \{0,1\}$. There are four maps $2 \to 2$, we give them names: the identity map $i$, the constant map $0$, the constant map $1$, and the twist map $t$.</p>

<p>An object in the topos of $M$-sets is a set $S$ with a right $M$ action, which is a map $s : S \times M \to S$ satisfying $s(x, i) = x$ and $s(x, f \circ g) = s(s(x, f), g)$. Since there are only four elements in $M$, we might as well figure out what this means. Let $S_0 = \{x \in S \mid \exists y \in S \,.\, x = s(y, 0)\}$ be the set of those elements of $S$ that arise as actions of~$0$. We define $S_1$ similarly. Because $0 \circ g = 0$, it follows for every $g \in M$ and $x \in S_0$ that
$$s(x, g) = s(s(y,0), g) = s(y, 0 \circ g) = s(y, 0) = x.$$
So, the elements of $S_0$ are fixed by the action. Similarly, the elements of $S_1$ are fixed by the action.</p>

<p>To every $M$-set $(S,s)$ we associate a graph $G_S$ as follows. The vertices of $G_S$ are the elements of $S_0 \cup S_1$. The <em>half-edges</em> of $G_S$ are the elements of $S$. Given a half-edge $e \in S$, its <em>source</em> is the vertex $s(e, 0)$. The <em>opposite</em> half-edge of $e$ is $S(e, t)$, and because $t \circ t = 1$, tit follows that the opposite of the opposite is the original half-edge. An <em>edge</em> is a half-edge together with its opposite. The <em>target</em> of a half-edge is the source of its opposite half-edge, i.e., the target of $e$ is $s(s(e,t),0) = s(e,1)$. (There is an anomaly which we allow: a half-edge may be its own opposite.)</p>

<p>What sort of graphs did we get? They are <em>symmetric graphs</em> in which each edge consists of two half-edges. An edge may be <em>degenerate</em> when it is composed of two copies of the same half-edge. In addition, the graphs are <em>reflexive</em> in the sense that each vertex has a distinguished degenerate loop starting and ending at the vertex (this is because $S_0 \cup S_1 \subseteq S$).</p>

<p>Exercise: figure out what the morphisms are, and then show that the description in terms of reflexive symmetric graphs gives a category that it equivalent to the topos of $M$-sets.</p>

<p>Is this the sort of thing you were asking about?</p>

CC BY-SA 4.0
2018-05-12T15:31:56.780Z
Yes, I was just interested broadly in whether the principles one can apply from category theory have been formalized to the study of graphs in some way. I wasn't sure what to expect, and this was definitely interesting!
MT_
CC BY-SA 4.0
2018-05-12T19:40:36.987Z
Here's another observation which I worked out once: the directed graphs that satisfy the principle of choice are precisely those whose in -and out-degrees are bounded by 1 (so every vertex has at most one edge coming in, and at most one edge coming out). Therefore, such graphs must be disjoint sums of cycles and paths.
Andrej Bauer
CC BY-SA 4.0
2018-05-13T19:43:28.300Z
What do you mean by the principle of choice?
MT_
CC BY-SA 4.0
2018-05-14T09:56:08.320Z
An object $X$ *satisfies choice* if for all $Y$ and $R$, $(\forall x \in X \exists y \in Y . R(x,y)) \Rightarrow \exists f \in Y^X \forall x \in X . R(x, f(x))$ in the internal language of the topos. This is equivalent to $X$ being internally projective, and is equivalent to the functor ${-}^X$ preserving epis.
Andrej Bauer
CC BY-SA 4.0
2018-05-14T10:50:19.923Z
I forgot to say that this is the topos-theoretic way of saying that an objects $X$ satisfies choice when every $X$-indexed family of inhabited sets has a choice function. For instance, countable choice is the same thing as $\mathbb{N}$ satisfying choice.
Andrej Bauer
CC BY-SA 4.0
2019-05-28T05:18:27.670Z
@AndrejBauer Where did you work out this "choice iff in/out degrees bounded by 1"?
Basil
CC BY-SA 4.0
2018-05-11T13:19:17.917Z
2018-05-11T13:19:17.917Z
Andrej Bauer
<p>I'm not sure about your connection to the natural number category, but there has definitely been some investigation of using the category of graph homomorphisms to describe colorings. See in particular <a href="https://en.wikipedia.org/wiki/Gallai%E2%80%93Hasse%E2%80%93Roy%E2%80%93Vitaver_theorem#Category-theoretic_interpretation" rel="nofollow noreferrer">this wikipedia page</a> which describes colorings as homomorphisms to the complete graph, and formulates the GHRV theorem as a statement in the category of homomorphisms of directed graphs: a directed graph has a homomorphism to a $k$-vertex transitive tournament if and only it does not have a homomorphism from a $(k+1)$-vertex path.</p>

CC BY-SA 4.0
2018-05-12T11:58:45.313Z
See also [this post](https://golem.ph.utexas.edu/category/2013/04/colouring_a_graph.html) by Tom Leinster at the n-Category Café.
Tobias Fritz
CC BY-SA 4.0
2018-05-12T12:00:47.257Z
It's also fascinating that the categorical dual gives the clique number: the homomorphisms $K_n\to G$ are exactly the $n$-cliques in $G$.
Tobias Fritz
CC BY-SA 4.0
2018-05-12T19:38:33.267Z
But has anyone actually sovled an interesting graph theoretic problems using this stuff?
Andrej Bauer
CC BY-SA 4.0
2018-05-11T21:08:53.457Z
2018-05-12T19:33:13.950Z
2018-05-12T19:33:13.950Z
David Eppstein
<p>I was fooling around with some concept and was wondering if this viewpoint is explored at all. Let INJ-GRAPH be the subcategory of graphs (with morphisms as homomorphisms) whose morphisms consist only of the graph homomorphisms which are injective as sets. Then clearly for such a homomorphism $f : G \to H$ of graphs, the chromatic number of $H$ is at least as large as the chromatic number of $G$. Thus one gets a covariant functor from INJ-GRAPH to the order category of $\mathbb{N}$ (i.e. the category whose objects are natural numbers and there is a unique arrow $a \to b$ if and only if $a \leq b$)</p>

<p>What's more is that this functor preserves coproducts. Indeed the coproduct of two graphs is given by the disjoint union of the graphs, and the chromatic number of this graph is the maximum of the chromatic number of the two graphs. I'm unsure if it preserves more general colimits, but I think at least if they are small then it should be ok.</p>

<p>Anyway, the question is, has this kind of category-theoretic reasoning been investigated in the literature? It currently seems like abstract nonsense, but perhaps it is indicative of something deeper.</p>

<graph-theory><ct.category-theory>
The chromatic number of a graph as a functor
MT_
# The chromatic number of a graph as a functor

(Asked by: username_0 on 2018-05-11)

I was fooling around with some concept and was wondering if this viewpoint is explored at all. Let INJ-GRAPH be the subcategory of graphs (with morphisms as homomorphisms) whose morphisms consist only of the graph homomorphisms which are injective as sets. Then clearly for such a homomorphism $f : G \to H$ of graphs, the chromatic number of $H$ is at least as large as the chromatic number of $G$. Thus one gets a covariant functor from INJ-GRAPH to the order category of $\mathbb{N}$ (i.e. the category whose objects are natural numbers and there is a unique arrow $a \to b$ if and only if $a \leq b$)

What's more is that this functor preserves coproducts. Indeed the coproduct of two graphs is given by the disjoint union of the graphs, and the chromatic number of this graph is the maximum of the chromatic number of the two graphs. I'm unsure if it preserves more general colimits, but I think at least if they are small then it should be ok.

Anyway, the question is, has this kind of category-theoretic reasoning been investigated in the literature? It currently seems like abstract nonsense, but perhaps it is indicative of something deeper.

**Tags:** graph-theory, ct.category-theory

---

## 2 answers

### Answer by username_1 on 2018-05-11. Score: 4 | Accepted answer

Sure, category theorists know such things, but I think for the difficult results that graph theorists care about, the generalities of category theory may at best help as an organizing principle. This is a bit similar to the theory of combinatorial species, which is a way of doing combinatorics inspired by category theory.

Here are some other basic observations, you can read more about such things in Lawvere's [Qualitative distinctions between some toposes of generalized graphs](https://github.com/mattearnshaw/lawvere/blob/master/pdfs/1989-qualitative-distinctions-between-some-toposes-of-generalized-graphs.pdf), Categories in computer science and logic (Boulder, CO, 1987), volume 92 of Contemporary Mathematics, 261–299. American Mathematical Society.

The category of directed graphs is a presheaf topos on the site consisting of two parallel arrows (so that a presheaf is given by two sets $E$ and $V$ and maps $t : E \to V$ and $s : E \to V$), see [A Guided Tour in the Topos of Graphs](https://arxiv.org/abs/math/0306394) by Sebastiano Vigna.

For any given $n$, the category of $n$-colored graphs is a topos, because it is just the slice of the topos of graphs over the complete graph on $n$ vertices (an $n$-coloring of $G$ is just a morphism $G \to K\_n$).

As Lawvere explains, several other categories of graphs are toposes because they are (equivalent to) toposes of monoid actions for a suitably chosen $M$. Let's just do one. Consider the monoid $M$ of endomaps on $2 = \{0,1\}$. There are four maps $2 \to 2$, we give them names: the identity map $i$, the constant map $0$, the constant map $1$, and the twist map $t$.

An object in the topos of $M$-sets is a set $S$ with a right $M$ action, which is a map $s : S \times M \to S$ satisfying $s(x, i) = x$ and $s(x, f \circ g) = s(s(x, f), g)$. Since there are only four elements in $M$, we might as well figure out what this means. Let $S\_0 = \{x \in S \mid \exists y \in S \,.\, x = s(y, 0)\}$ be the set of those elements of $S$ that arise as actions of~$0$. We define $S\_1$ similarly. Because $0 \circ g = 0$, it follows for every $g \in M$ and $x \in S\_0$ that
$$s(x, g) = s(s(y,0), g) = s(y, 0 \circ g) = s(y, 0) = x.$$
So, the elements of $S\_0$ are fixed by the action. Similarly, the elements of $S\_1$ are fixed by the action.

To every $M$-set $(S,s)$ we associate a graph $G\_S$ as follows. The vertices of $G\_S$ are the elements of $S\_0 \cup S\_1$. The *half-edges* of $G\_S$ are the elements of $S$. Given a half-edge $e \in S$, its *source* is the vertex $s(e, 0)$. The *opposite* half-edge of $e$ is $S(e, t)$, and because $t \circ t = 1$, tit follows that the opposite of the opposite is the original half-edge. An *edge* is a half-edge together with its opposite. The *target* of a half-edge is the source of its opposite half-edge, i.e., the target of $e$ is $s(s(e,t),0) = s(e,1)$. (There is an anomaly which we allow: a half-edge may be its own opposite.)

What sort of graphs did we get? They are *symmetric graphs* in which each edge consists of two half-edges. An edge may be *degenerate* when it is composed of two copies of the same half-edge. In addition, the graphs are *reflexive* in the sense that each vertex has a distinguished degenerate loop starting and ending at the vertex (this is because $S\_0 \cup S\_1 \subseteq S$).

Exercise: figure out what the morphisms are, and then show that the description in terms of reflexive symmetric graphs gives a category that it equivalent to the topos of $M$-sets.

Is this the sort of thing you were asking about?

> **Comments:**
> **username_0**: Yes, I was just interested broadly in whether the principles one can apply from category theory have been formalized to the study of graphs in some way. I wasn't sure what to expect, and this was definitely interesting!  
> **username_1**: Here's another observation which I worked out once: the directed graphs that satisfy the principle of choice are precisely those whose in -and out-degrees are bounded by 1 (so every vertex has at most one edge coming in, and at most one edge coming out). Therefore, such graphs must be disjoint sums of cycles and paths.  
> **username_0**: What do you mean by the principle of choice?  
> **username_1**: An object $X$ *satisfies choice* if for all $Y$ and $R$, $(\forall x \in X \exists y \in Y . R(x,y)) \Rightarrow \exists f \in Y^X \forall x \in X . R(x, f(x))$ in the internal language of the topos. This is equivalent to $X$ being internally projective, and is equivalent to the functor ${-}^X$ preserving epis.  
> **username_1**: I forgot to say that this is the topos-theoretic way of saying that an objects $X$ satisfies choice when every $X$-indexed family of inhabited sets has a choice function. For instance, countable choice is the same thing as $\mathbb{N}$ satisfying choice.  
> **username_2**: @AndrejBauer Where did you work out this "choice iff in/out degrees bounded by 1"?  

---

### Answer by username_3 on 2018-05-11. Score: 4

I'm not sure about your connection to the natural number category, but there has definitely been some investigation of using the category of graph homomorphisms to describe colorings. See in particular [this wikipedia page](https://en.wikipedia.org/wiki/Gallai%E2%80%93Hasse%E2%80%93Roy%E2%80%93Vitaver_theorem#Category-theoretic_interpretation) which describes colorings as homomorphisms to the complete graph, and formulates the GHRV theorem as a statement in the category of homomorphisms of directed graphs: a directed graph has a homomorphism to a $k$-vertex transitive tournament if and only it does not have a homomorphism from a $(k+1)$-vertex path.

> **Comments:**
> **username_4**: See also [this post](https://golem.ph.utexas.edu/category/2013/04/colouring_a_graph.html) by Tom Leinster at the n-Category Café.  
> **username_4**: It's also fascinating that the categorical dual gives the clique number: the homomorphisms $K_n\to G$ are exactly the $n$-cliques in $G$.  
> **username_1**: But has anyone actually sovled an interesting graph theoretic problems using this stuff?  

---

