Graph homomorphism

Not to be confused with graph homeomorphism.

Graph homomorphism from J5 into C5
A homomorphism from the flower snark J5 into the cycle graph C5.
It is also a retraction onto the subgraph on the central five vertices. Thus J5 is in fact homo­mor­phi­cally equivalent to the core C5.

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.[1] The fact that homomorphisms can be composed leads to rich algebraic structures: a preorder on graphs, a distributive lattice, and a category (one for undirected graphs and one for directed graphs).[2] 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.[3]

  1. ^ Hell & Nešetřil 2004, p. 27.
  2. ^ Hell & Nešetřil 2004, p. 109.
  3. ^ Hell & Nešetřil 2008.