A graph homomorphism from a graph to a graph, written, is a mapping from the vertex set of to the vertex set of such that implies .
The above definition is extended to directed graphs. Then, for a homomorphism, is an arc of if is an arc of .
If there exists a homomorphism we shall write, and otherwise. If, is said to be homomorphic to or -colourable.
If the homomorphism is a bijection whose inverse function is also a graph homomorphism, then is a graph isomorphism.
Two graphs and are homomorphically equivalent if and .
A retract of a graph is a subgraph of such that there exists a homomorphism, called retraction with for any vertex of . A core is a graph which does not retract to a proper subgraph. Any graph is homomorphically equivalent to a unique core.
Read more about Graph Homomorphism: Properties, Connection To Coloring and Girth, Complexity
Famous quotes containing the word graph:
“When producers want to know what the public wants, they graph it as curves. When they want to tell the public what to get, they say it in curves.”
—Marshall McLuhan (1911–1980)