In the mathematical field of graph theory a graph homomorphism is a mapping between two graphs that respects their structure. More concretely it maps

• vertices to vertices
• undirected edges to undirected edges or collapses the edge onto a vertex.
• directed edges to directed edges (without changing direction) or collapses the edge onto a vertex

Contents

1 Definition 2 Examples 3 Notes 4 See also

Definition

A graph homomorphism <math>f<math> from a graph <math>G:=(V,E)<math> to a graph <math>G':=(V',E')<math> is a function

<math>f:V \cup E \to V' \cup E'<math>

on the edges and vertices of <math>G<math> such that

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

The above definition works even when <math>G<math> and <math>G'<math> are allowed to have multiedges and loops. In the case of simple graphs, the definition can is slightly simpler: where an edge maps is determined by where its endpoints map.

Some authors use a stricter definition than the one given here, in which an edge is not allowed to map to a vertex. Thus, if the destination graph has no loops, adjacent vertices can't map to the same vertex.

If the homomorphism <math>f<math> is a bijection, then the inverse function is also a graph homomorphism, so <math>f<math> is a graph isomorphism. In this case, the two graphs are identical from the viewpoint of graph theory.

Examples

The function

<math>f:G \to K_1<math>

mapping a graph <math>G<math> to the complete graph with one vertex is a graph homomorphism.

Notes

In terms of graph coloring, a k-coloring of G, without restrictions, is equivalent to a homomorphism of G into K_k, the complete graph on k vertices. (Each vertex of <math>G<math> is colored according to which vertex of <math>K_k<math> it goes to.) As an extension of that analogy, a homomorphism of G into H is also sometimes called an H-coloring.

A graph H is a subgraph of G if and only if there exists a monomorphism <math>f:H\to G<math>.

See also

• Graph rewriting