A weaker concept of graph homomorphism

Question

In the category $\mathsf{Graph}$ of simple graphs with graph homomorphisms we'll find the following situation (the big circles indicating objects, labelled by the graphs they enclose, arrows indicating the existence of a homomorphism):

Speaking informally, the "obvious" structural relatedness between the two circle graphs $C_3$ and $C_4$ reduces to its two common subgraphs $P_3$ and $P_4$, with $P_3$ being a subgraph of $P_4$.

But even though there is an "undeniable" structural relatedness between $C_3$ and $C_4$, there is no single graph homomorphism between the two. This in complete contrast to the category $\mathsf{Top}$, where they are even isomorphic. (Instead of this: no arrows between $P_i$ and $C_j$!)

But why is there no graph homomorphism between $C_3$ and $C_4$? There are two interrelated reasons:

1. If all vertices of a graph were forced to have a self-loop, there would be a homomorphism from $C_4$ to $C_3$, since two adjacent vertices $x,y$ were allowed to be mapped onto the same vertex $f(x)=f(y)$. Furthermore, there would also be a homomorphism from $P_4$ to $P_3$.

2. If one insists on graphs to be loop-less (as in topological graph theory?), one might instead weaken the definition of a graph homomorphism. Instead of defining $f:G\rightarrow G'$ to be a homomorphism when $(x,y) \in E(G)$ implies $(f(x),f(y)) \in E(G')$, one might define it like this:
   

   $f:G\rightarrow G'$ is a (weak) homomorphism when $(x,y) \in E(G)$ implies $f(x) = f(y) \vee (f(x),f(y)) \in E(G')$.

My questions are:

1. In which contexts does this definition of a (weak) homomorphism between simple graphs have drawbacks other than not being standard, e.g. technical ones?

2. Is there a known or imaginable "problem" that might be easier to handle with weak homomorphisms (other than the missing homomorphism between $C_4$ and $C_3$ which isn't really a problem)?

3. Might weak homomorphisms be conceptually more appropriate, i.e. catch the "meaning" of structure preserving better?

4. Where can I find weak homomorphisms in the literature, maybe under another name?

Answer 1

What you call a weak homomorphism is just a simplicial map where we view graphs as 1-dimensional simplicial complexes. In my opinion these are very natural and important outside of the coloring context. Here are my reasons:

1. The endomorphism monoid is much richer if you allow simplicial maps. The endomorphism of the complete graph are only automorphisms under the rigid definition. Using simplicial maps it is all maps on the vertices.

2. You cannot contract a spanning tree with the rigid definition.

3. I defined orbital graphs for transformation monoids to generalize D. Higman's theorem but the monoid must be allowed to crush edges for it to work.

Adding loops is not a good solution in my opinion because it changes the fundamental group and homology. For instance, if a monoid acts on a graph by simplicial maps, then the chain groups become modules. Adding loops gives the wrong effect since crushing an edge should give the zero map.

Answer 2

What you are describing is sometimes goes under the phrase reflexive vs. irreflexive graphs. What you seem to be describing are two categories:

• Irreflexive graphs: the objects are sets with irreflexive symmetric relations, the morphisms are relation-preserving functions on the underlying sets.

• Reflexive graphs: the objects are sets with reflexive symmetric relations, the morphisms are relation-preserving functions on the underlying sets.

It is fun to compute cartesian products in both of these and to discover the two well-known kinds of graph products. Graph theorists could benefit from a bit of category theory.

There are actually many variations on categories of graphs. Here are some others.

Graphs as relations

The categories of relations and relation-preserving functions are categories of simple graphs. We can require various additional properties. Symmetric relations give us symmetric graphs, reflexive relations give us graphs in which morphisms are allowed to squish edges, etc.

Directed graphs

This is perhaps the most straightforward example. Let $\mathcal{C}$ be the category with two objects, called $\mathsf{E}$ and $\mathsf{V}$ and two arrows $\mathsf{s}, \mathsf{t} : \mathsf{E} \to \mathsf{V}$. Then the (covariant) presheaf category $\mathbf{Set}^\mathcal{C}$ is just the category of directed graphs. An object of the category can be viewed as a pair of sets $(E, V)$ together with two maps $s, t : E \to V$.

Reflexive directed graphs

We can play with directed graphs. For example, if we add an arrow $\mathsf{r} : \mathsf{V} \to \mathsf{E}$ which is a common right inverse of $\mathsf{s}$ and $\mathsf{t}$, we obtain directed graphs with chosen loops.

Symmetric graphs

Another option is to add an arrow $\mathsf{o} : \mathsf{E} \to \mathsf{E}$ satisfying $\mathsf{t} \circ \mathsf{o} = \mathsf{s}$ and $\mathsf{o} \circ \mathsf{o} = \mathsf{o}$ (yes, I am using different kinds of circles on purposes to confuse you). The presheaf category then corresponds to directed graphs in which each edge $e : a \to b$ has an opposite $o(e) : b \to a$, and "opposite" is an involution. It may happen that a loop is its own opposite.

Graphs as monoid actions

To get more fun out of categories of graphs we can do the following. Let $M$ be the monoid of functions $\lbrace 0, 1 \rbrace \to \lbrace 0, 1 \rbrace$. There are four elements, the identity $1$, the map $t$ which swaps $0$ and $1$, and the two constant maps $0$ and $1$. The category of right $M$-actions can be seen as a category of graphs.

Suppose $(X, m : X \times M \to X)$ is a right action on $X$. This is a graph in the following sense. The vertices are those elements of $X$ that are fixed by the action of $0$, or equivalently by the action of $1$. We do not have edges, but rather "half-edges". A half-edge is an element of $X$ which is not a vertex. Each half edge $e$ has its mate $e \cdot t$, and together you can think of them as a wholesome edge (unordered). A half-edge $e$ is attached to the vertex $e \cdot 0$, while its mate is attached to $e \cdot 1$.

We almost get the usual symmetric (non-simple) graphs, except that there can be degenerate half-edges that are their own mates (and therefore necessarily loop-like).

The relevant reference for this answer is Bill Lawvere's Categories of spaces may not be generalized spaces as exemplified by directed graphs.