Talk:Graph homomorphism

Template:Tmbox[[Category:Template:GA/Topic good articles|Graph homomorphism]] Template:WikiProject banner shell

Definition issue

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:41, 12 Jan 2005 (UTC)

I extended your definition slightly to clarify the domain and codomain of f, because later we talk about bijection and it has to be clear where the f is defined. Otherwise I think your definition is easier to understand and the article is now in a useable state.MathMartin 10:19, 25 Jan 2005 (UTC)

WRONG DEFINITION

I do not agree with this definition at all: it might be a good definition for a graph contraction but not for graph homomorphism.

One of the fundamental property of graph homomorphism is that a graph G is k colorable iff G has a homomorphism to the complete graph on k vertices. This is the reason why the property to have a homomorphism to some fixed graph H is called 'H-colorability'. According to your definition, every graph has a homomorphism to $K_1$.

Th standard definition of a homomorphism is the following: A homorphism from a graph G to a graph H is a mapping from the vertex set of G to the vertex set of H so that two adjacent vertices of G are mapped to two adjacent vertices of H. This definition can easily be extended to directed graphs and to graphs with loops (if v has a loop attached, v is adjacent to v thus f(v) is adjacent to f(v), that is: f(v) has a loop attached). Extension to multigraphs is not usual at all.

Reference:

P. Hell and J. Nesetril, Graphs and Homorphisms, Oxford Lecture Series in Mathematics and its Applications 28, Oxford University Press, 2004.

pom 11:25, 13 November 2005 (UTC)

I think that terms weak and strong homomorphism need to be introduced. Weak homomorphism does not take the directions of lines into account while strong does. A proper definition should introduce two functions, f1 and f1 where f1 maps vertices and f2 maps lines. If these two functions are bijections and there is a (strong, weak) homomorphism, we have a (strong, weak) graph isomorphism. --212.235.208.165 (talk) 10:41, 24 November 2008 (UTC)