Talk:Graph homomorphism

From Wikipedia, the free encyclopedia

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

Wikipedia's being slow and flaky
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)

[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

if $v w$ is an edge of $G$ , then $f (v) f (w)$ is an edge of $H$ , or $f (v) = f (w)$ , and
if $v w$ 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

vertices of $G$ go to vertices of $H$ ,
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
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 $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)

Retrieved from "http://en.wikipedia.org../../../g/r/a/Talk%7EGraph_homomorphism_a4fb.html"

Talk:Graph homomorphism

From Wikipedia, the free encyclopedia

[edit] Simpler definition

[edit] WRONG DEFINITION

Views

Navigation

Search