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.

Homomorphism generalize various notions of graph colorings and allow to express an important class of constraint satisfaction problems, such as certain scheduling or frequency assignment problems.

A graph homomorphism f  from a graph G = (V(G), E(G)) to a graph H = (V(H), E(H)), written

is a mapping f : V(G) → V(H) such that {u,v} ∈ E(G) implies {f(u),f(v)} ∈ E(H), for all u, v ∈ V(G). If there exists any homomorphism f : G → H, then G is said to be homomorphic to H or H-colorable, we shall write:

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.

If the homomorphism f : G → H is an injection, then G is simply a subgraph of H. If the homomorphism is a bijection whose inverse function is also a graph homomorphism, then f is a graph isomorphism. If the homomorphism is a surjection that is locally bijective, that is, it is bijective on the neighbourhood of each vertex, then f is called a covering map, mirroring the definition and many properties of covering maps in topology.

...
Wikipedia