Graph homomorphism
From Wikipedia, the free encyclopedia
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.
Contents |
[edit] Definition
A graph homomorphism f from a graph G: = (V,E) to a graph G': = (V',E'), written 
is a mapping 
from the vertex set of G to the vertex set of G' such that 
whenever 
.
The above definition is extended to directed graphs. Then, for a homomorphism , (f(u),f(v)) is an arc of G' if (u,v) is an arc of G.
If there exists a homomorphism 
we shall write 
, and 
otherwise. If , G is said to be homomorphic to H or H-colourable.
The composition of homomorphisms are homomorphisms. If the homomorphism is a bijection whose inverse function is also a graph homomorphism, then f is a graph isomorphism. Determining whether there is an isomorphism between two graphs is an important problem in computational complexity theory; see graph isomorphism problem.
Two graphs G and G' are homomorphically equivalent if 
and 
.
A retract of a graph G is a subgraph H of G such that there exists a homomorphism 
, 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.
[edit] Notes
- In terms of graph coloring, k-colourings of G are precisely homomorphisms
. As a consequence if , the chromatic number of G is at most the one of H: χ(G) ≤ χ(H). - if , the odd girth of G is at least the one of H.
- Graph homomorphism preserves connectedness.
- The tensor product of graphs is the category-theoretic product for the category of graphs and graph homomorphisms.
- The associated decision problem, i.e. deciding whether there exists a homomorphism from one graph to an other, is NP-complete.
[edit] References
- Hell, Pavol; Jaroslav Nešetřil (2004). Graphs and Homomorphisms (Oxford Lecture Series in Mathematics and Its Applications). Oxford University Press. ISBN 0-19-852817-5.
