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 is a function between the vertex sets of two graphs that maps adjacent vertices to adjacent vertices. Homomorphisms generalize various notions of graph colorings and allow the expression of an important class of constraint satisfaction problems, such as certain scheduling or frequency assignment problems. The fact that homomorphisms can be composed leads to rich algebraic structures: a preorder on graphs, a distributive lattice, and a (one for undirected graphs and one for directed graphs). The computational complexity of finding a homomorphism between given graphs is prohibitive in general, but a lot is known about special cases that are solvable in polynomial time. Boundaries between tractable and intractable cases have been an active area of research. In this article, unless stated otherwise, graphs are finite, undirected graphs with loops allowed, but multiple edges (parallel edges) disallowed. A graph homomorphism f from a graph to a graph , written f : G → H is a function from to that maps endpoints of each edge in to endpoints of an edge in . Formally, implies , for all pairs of vertices in . If there exists any homomorphism from G to H, then G is said to be homomorphic to H or H-colorable. This is often denoted as just G → H . The above definition is extended to directed graphs. Then, for a homomorphism f : G → H, (f(u),f(v)) is an arc (directed edge) of H whenever (u,v) is an arc of G. There is an injective homomorphism from G to H (i.e., one that never maps distinct vertices to one vertex) if and only if G is a subgraph of H. If a homomorphism f : G → H is a bijection (a one-to-one correspondence between vertices of G and H) whose inverse function is also a graph homomorphism, then f is a graph isomorphism. Covering maps are a special kind of homomorphisms that mirror the definition and many properties of covering maps in topology. They are defined as surjective homomorphisms (i.