Talk:Graph homomorphism

The definition is wrong. For example, in the condition

• δ_E = δ_E′ o f_E

the range of the left side is sets of E-vertices, while the range of the right side is sets of E'-vertices.

I'm not correcting it right now because

1. Wikipedia's being slow and flaky
2. I don't have a reference for this concept.

Anyway, I suspect it could be stated a lot more simply, without so much formalism. Dbenbenn 21:42, 9 Jan 2005 (UTC)

You are right the definition is wrong. I will fix it in the next few days. As for the simplicity: What I really meant to do is draw some commutative diagrams. The obscure equations are just placeholders until I have created the diagrams. MathMartin 13:03, 10 Jan 2005 (UTC)

It appears that the map from a graph to $K_{1}$ is not a graph homomorphism. I find that surprising; I think it should be mentioned explicitly. Dbenbenn 15:20, 10 Jan 2005 (UTC)

You are correct again. I have to modify the functions to allow for the removal of edges and arrows by mapping them onto vertices. MathMartin 17:08, 10 Jan 2005 (UTC)

Now the definition should be correct, but I will still try to make it more clear. MathMartin 14:01, 12 Jan 2005 (UTC)

Simpler definition

The new definition looks correct, but scary! What do you think of the following simplification?

A graph homomorphism $f$ from a graph $G$ to a graph $H$ maps vertices of $G$ to vertices of $H$ such that

1. if $vw$ is an edge of $G$, then $f(v)f(w)$ is an edge of $H$, or $f(v)=f(w)$, and
2. if $vw$ is a directed edge of $G$, then $f(v)f(w)$ is a directed edge of $H$ (in the same direction), or $f(v)=f(w)$.

Basically, we don't really need to talk about the homomorphism's values on the edges, since that value is determined by the value on vertices. Dbenbenn 14:27, 12 Jan 2005 (UTC)

Your definition is simpler but only valid for homomorphisms between simple graphs. I understand your concerns, I do not like the definition either and I will try to make it clearer. Perhaps it would be best to include both definitions and point out the difference ? MathMartin 16:46, 12 Jan 2005 (UTC)

Oh, right. The problem is that with either loops or multiedges, the definition of "monomorphism" gets broken. How about the following slightly less simple version:

A graph homomorphism $f$ from a graph $G$ to a graph $H$ is a function on the edges and vertices of $G$ such that

1. vertices of $G$ go to vertices of $H$,
2. if $e$ is an edge of $G$ with endpoints $v$ and $w$ then either $f(e)$ is an edge of $H$ with endpoints $f(v)$ and $f(w)$, or $f(e)=f(v)=f(w)$, and
3. if $e$ is a directed edge of $G$ from $v$ to $w$ then either $f(e)$ is a directed edge of $H$ from $f(v)$ to $f(w)$, or $f(e)=f(v)=f(w)$.

By the way, the definition in the article is still slightly broken. Where does $\delta _{A}$ send a vertex $v$ in the range $V\times V$? Dbenbenn 21:40, 12 Jan 2005 (UTC)