User:Tokenzero/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 is a function between the vertex sets of two graphs that maps adjacent vertices to adjacent vertices.
This is not a Wikipedia article: It is an individual user's work-in-progress page, and may be incomplete and/or unreliable. Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
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 reasearch.[3]