Graph homomorphism

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

Definitions

A graph homomorphism $f$ from a graph $G=(V,E)$ to a graph $G'=(V',E')$, written $f:G \rightarrow G'$, is a mapping $f:V \rightarrow V'$ from the vertex set of $G$ to the vertex set of $G'$ such that $\{u,v\}\in E$ implies $\{f(u),f(v)\}\in E'$.

The above definition is extended to directed graphs. Then, for a homomorphism $f:G \rightarrow G'$, $(f(u),f(v))$ is an arc of $G'$ if $(u,v)$ is an arc of $G$.

If there exists a homomorphism $f:G\rightarrow H$ we shall write $G\rightarrow H$, and $G\not\rightarrow H$ otherwise. If $G\rightarrow H$, $G$ is said to be homomorphic to $H$ or $H$-colourable.

If the homomorphism $f:G\rightarrow G'$ is a bijection whose inverse function is also a graph homomorphism, then $f$ is a graph isomorphism.

Two graphs $G$ and $G'$ are homomorphically equivalent if $G\rightarrow G'$ and $G'\rightarrow G$.

A retract of a graph $G$ is a subgraph $H$ of $G$ such that there exists a homomorphism $r:G\rightarrow H$, called retraction with $r(x)=x$ for any vertex $x$ of $H$. A core is a graph which does not retract to a proper subgraph. Any graph is homomorphically equivalent to a unique core.

Properties

The composition of homomorphisms are homomorphisms.

Graph homomorphism preserves connectedness.

The tensor product of graphs is the category-theoretic product for the category of graphs and graph homomorphisms.

Connection to coloring and girth

A graph coloring is an assignment of one of k colors to each vertex of a graph G so that the endpoints of each edge have different colors, for some number k. Any coloring corresponds to a homomorphism $f:G\rightarrow K_k$ from G to a complete graph K_k: the vertices of K_k correspond to the colors of G, and f maps each vertex of G with color c to the vertex of K_k that corresponds to c. This is a valid homomorphism because the endpoints of each edge of G are mapped to distinct vertices of K_k, and every two distinct vertices of K_k are connected by an edge, so every edge in G is mapped to an adjacent pair of vertices in K_k. Conversely if f is a homomorphism from G to K_k, then one can color G by using the same color for two vertices in G whenever they are both mapped to the same vertex in K_k. Because K_k has no edges that connect a vertex to itself, it is not possible for two adjacent vertices in G to both be mapped to the same vertex in K_k, so this gives a valid coloring. That is, G has a k-coloring if and only if it has a homomorphism to K_k.

If there are two homomorphisms $H\rightarrow G\rightarrow K_k$, then their composition $H\rightarrow K_k$ is also a homomorphism. In other words, if a graph G can be colored with k colors, and there is a homomorphism $H\rightarrow G$, then H can also be k-colored. Therefore, whenever a homomorphism $H\rightarrow G$ exists, the chromatic number of H is less than or equal to the chromatic number of G.

Homomorphisms can also be used very similarly to characterize the odd girth of a graph G, the length of its shortest odd-length cycle. The odd girth is, equivalently, the smallest odd number g for which there exists a homomorphism $C_g\rightarrow G$. For this reason, if $G\rightarrow H$, then the odd girth of G is greater than or equal to the corresponding invariant of H.^[1]

Complexity

The associated decision problem, i.e. deciding whether there exists a homomorphism from one graph to another, is NP-complete. Determining whether there is an isomorphism between two graphs is also an important problem in computational complexity theory; see graph isomorphism problem.

See also

• Hadwiger's conjecture.
• Graph rewriting
• Median graphs, definable as the retracts of hypercubes.

Notes

1. Hell & Nešetřil (2004), p. 7.

References

• Hell, Pavol; Nešetřil, Jaroslav (2004), Graphs and Homomorphisms (Oxford Lecture Series in Mathematics and Its Applications), Oxford University Press, ISBN 0-19-852817-5
• Brown, R.; Morris, I.; Shrimpton, J.; Wensley, C. D. (2008), "Graphs of morphisms of graphs", Electronic Journal of Combinatorics 15 (1): A1