Graph theory from a category theory perspective

Question

Are there any textbooks on graph theory written for a category theorist?

It would probably have to be on directed graph theory, but if there's some trick we can use to talk about undirected graphs as well that would be interesting.

A little more specifically, I'm looking for a text that begins by defining directed graphs and paths, then defines the obvious category out of a given directed graph with paths as arrows, then proceeds to derive results about directed graphs using these categories.

Most connections I see made between category theory and graph theory are in the other direction, taking the underlying graph of a category and saying something about it to derive a result about the category, but as someone comfortable with categories and not comfortable with graphs this approach isn't particularly illuminating.

Further, unless I'm mistaken, these constructions amount to an equivalence (maybe even an isomorphism?) between the category of directed graphs and the category of categories, so it feels like we should be able to say something about directed graphs from this perspective.

Any references are appreciated.

Answer 1

A few points:

1. The category of graphs is certainly not equivalent to the category of categories. But they are related (for more on that see (3)).

2. As you allude to, there are multiple categories of graphs to be interested in. I've had a go at naming some of them here, including directed/undirected, multi/simple, and various conditions on loops, trying to view them from a common framework as being certain categories of presheaves.

3. Let $Gph$ be the category of directed multigraphs (as usual for category theorists), and let $U: Cat \to Gph$ be the forgetful functor. As you point out, $U$ has a left adjoint $F: Gph \to Cat$, which sends a graph $\Gamma$ to the category of "paths" in $\Gamma$. This adjunction is even monadic, exhibiting $Cat$ as a category of algebras over $Gph$. In this way, it's reasonable to regard a category as a graph with extra structure. I'd hazard a guess that dually the functor $F: Gph \to Cat$ is maybe comonadic? (EDIT: Yes, I'm pretty sure that $F$ preserves all equalizers. It is clearly a conservative left adjoint between complete categories, so it's comonadic by the dual of the crude monadicity theorem.) In this way, it should be reasonable to regard a graph as a category with extra structure associated to being a free category. This would give some more justification for your approach of viewing a graph as a category with extra structure.

Answer 2

You may be interested with my work with Bisson, we have defined various closed models on category of graphs. In particular in the category of directed graphs. Consider the category $C$ which has two objects $0,1$ and two morphisms: $s,t:0\rightarrow 1$. A directed graph $G$ is a presheaf defined on $C$, that is two sets $G_0$ and $G_1$ where $G_0$ is the set of vertices here and $G_1$ the set of arrows $G(s):G_1\rightarrow G_0$ is the source map and $G(t)$ the target maps.

The category of undirected graphs can also be viewed as a topos, by adding in $C$ an involution $i:1\rightarrow 1$ such that $i\circ s=t$.

Bisson, Terrence, and Aristide Tsemo. "A homotopical algebra of graphs related to zeta series." Homology, Homotopy and Applications 11.1 (2009): 171-184.

Bisson, T., & Tsemo, A. (2011). Symbolic dynamics and the category of graphs. arXiv preprint arXiv:1104.1805.

Answer 3

Not quite what you're looking for, but the Handbook of Product Graphs does discuss the category of graphs, and which of the four products of graphs are appropriate from the point of view of category theory (hint: it's the categorical product, not the lexicographic product or the cartesian product). If you search this pdf for "category" you will find various little nuggets you might enjoy.

Answer 4

What you are describing is here. A (directed) graph is essentially a free category, ie the path category generated by the graph.

This construction is the left adjoint to the forgetful functor from Cats to the category of directed graphs.

This amount to an equivalence between the category of directed graphs and the category of free categories, not the entire Cat (which makes sense, a category can be presented from a free cat by imposing relations, ie commuting diagrams, aside the trivial ones. That side is invisible from the point of view of the underlying graph).

Now, on to the book: as far as I know, there isn't (though there are a few refs to the above, again look it up in the hyperlink). Such a book should investigate basic results of directed graph theory from the point of view of the theory of free categories. Not too sure it would help finding new facts in graph theory, but it is nevertheless an intriguing idea. After all, there is an entire industry on free groups, why not on free cats?

Answer 5

You may be interested in "Functorial Approach to Graph and Hypergraph Theory" by M. Schmidt. It contains plenty of adjunctions and gives examples of concrete constructions. It contains more than your average paper on categorical constructions on graphs. It is a generalization of the ideas contained in the paper "Categorical Constructions in Graph Theory" by Bumby and Latch. Even if it doesn't have exactly what you are looking for, it is an interesting look.