Graph homomorphism

Not to be confused with graph homeomorphism.

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 Kk: the vertices of Kk correspond to the colors of G, and f maps each vertex of G with color c to the vertex of Kk that corresponds to c. This is a valid homomorphism because the endpoints of each edge of G are mapped to distinct vertices of Kk, and every two distinct vertices of Kk are connected by an edge, so every edge in G is mapped to an adjacent pair of vertices in Kk. Conversely if f is a homomorphism from G to Kk, 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 Kk. Because Kk 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 Kk, so this gives a valid coloring. That is, G has a k-coloring if and only if it has a homomorphism to Kk.

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

Notes

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

References

This article is issued from Wikipedia - version of the Sunday, February 28, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.