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:
“In this Journal, my pen is a delicate needle point, tracing out a graph of temperament so as to show its daily fluctuations: grave and gay, up and down, lamentation and revelry, self-love and self-disgust. You get here all my thoughts and opinions, always irresponsible and often contradictory or mutually exclusive, all my moods and vapours, all the varying reactions to environment of this jelly which is I.”
—W.N.P. Barbellion (1889–1919)