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:
-
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$.
-
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:
-
In which contexts does this definition of a (weak) homomorphism between simple graphs have drawbacks other than not being standard, e.g. technical ones?
-
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)?
-
Might weak homomorphisms be conceptually more appropriate, i.e. catch the "meaning" of structure preserving better?
-
Where can I find weak homomorphisms in the literature, maybe under another name?
Best Answer
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:
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.
You cannot contract a spanning tree with the rigid definition.
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.