Talk:Graph homomorphism

From Wikipedia, the free encyclopedia

The definition is wrong. For example, in the condition

  • δE = δE′ o fE

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 K1 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)

[edit] 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 δ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)

[edit] 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 K1.

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)