 Graph homomorphism

Not to be confused with graph homeomorphism.
In the mathematical field of graph theory a graph homomorphism is a mapping between two graphs that respects their structure. More concretely it maps adjacent vertices to adjacent vertices.
Contents
Definitions
A graph homomorphism f from a graph G = (V,E) to a graph G' = (V',E'), written , is a mapping from the vertex set of G to the vertex set of G' such that implies .
The above definition is extended to directed graphs. Then, for a homomorphism , (f(u),f(v)) is an arc of G' if (u,v) is an arc of G.
If there exists a homomorphism we shall write , and otherwise. If , G is said to be homomorphic to H or Hcolourable.
If the homomorphism is a bijection whose inverse function is also a graph homomorphism, then f is a graph isomorphism.
Two graphs G and G' are homomorphically equivalent if and .
A retract of a graph G is a subgraph H of G such that there exists a homomorphism , called retraction with r(x) = x for any vertex x of H. A core is a graph which does not retract to a proper subgraph. Any graph is homomorphically equivalent to a unique core.
Properties
The composition of homomorphisms are homomorphisms.
Graph homomorphism preserves connectedness.
The tensor product of graphs is the categorytheoretic product for the category of graphs and graph homomorphisms.
Connection to coloring and girth
A graph coloring is an assignment of one of k colors to a graph G so that the endpoints of each edge have different colors, for some number k. Any coloring corresponds to a homomorphism from G to a complete graph K_{k}: the vertices of K_{k} correspond to the colors of G, and f maps each vertex of G with color c to the vertex of K_{k} that corresponds to c. This is a valid homomorphism because the endpoints of each edge of G are mapped to distinct vertices of K_{k}, and every two distinct vertices of K_{k} are connected by an edge, so every edge in G is mapped to an adjacent pair of vertices in K_{k}. Conversely if f is a homomorphism from G to K_{k}, then one can color G by using the same color for two vertices in G whenever they are both mapped to the same vertex in K_{k}. Because K_{k} has no edges that connect a vertex to itself, it is not possible for two adjacent vertices in G to both be mapped to the same vertex in K_{k}, so this gives a valid coloring. That is, G has a kcoloring if and only if it has a homomorphism to K_{k}.
If there are two homomorphisms , then their composition is also a homomorphism. In other words, if a graph G can be colored with k colors, and there is a homomorphism , then H can also be kcolored. Therefore, whenever a homomorphism exists, the chromatic number of H is less than or equal to the chromatic number of G.
Homomorphisms can also be used very similarly to characterize the girth of a graph G, the length of its shortest cycle, and the odd girth, the length of the shortest odd cycle. The girth is, equivalently, the smallest number g such that a cycle graph C_{g} has a homomorphism , and the odd girth is the smallest odd number g for which there exists a homomorphism . For this reason, if , then the girth and odd girth of G are both greater than or equal to the corresponding invariants of H.
Complexity
The associated decision problem, i.e. deciding whether there exists a homomorphism from one graph to another, is NPcomplete. Determining whether there is an isomorphism between two graphs is also an important problem in computational complexity theory; see graph isomorphism problem.
See also
 Hadwiger's conjecture.
 Graph rewriting
 Median graphs, definable as the retracts of hypercubes.
References
 Hell, Pavol; Jaroslav Nešetřil (2004). Graphs and Homomorphisms (Oxford Lecture Series in Mathematics and Its Applications). Oxford University Press. ISBN 0198528175.
Categories: Graph theory
 Morphisms
Wikimedia Foundation. 2010.
Look at other dictionaries:
Homomorphism — In abstract algebra, a homomorphism is a structure preserving map between two algebraic structures (such as groups, rings, or vector spaces). The word homomorphism comes from the Greek language: ὁμός (homos) meaning same and μορφή (morphe)… … Wikipedia
Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called colors to elements of a graph… … Wikipedia
Graph isomorphism — In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H such that any two vertices u and v of G are adjacent in G if and only if ƒ(u) and ƒ(v) are adjacent in H. This kind of bijection is commonly… … Wikipedia
Graph of groups — In geometric group theory, a graph of groups is an object consisting of a collection of groups indexed by the vertices and edges of a graph, together with a family of injective homomorphisms of the edge groups into the vertex groups.There is a… … Wikipedia
Induced homomorphism — In mathematics, an induced homomorphism is a structure preserving map between a pair of objects that is derived in a canonical way from another map between another pair of objects. A particularly important case arises in algebraic topology, where … Wikipedia
Conceptual graph — Conceptual graphs (CGs) are a formalism for knowledge representation. In the first published paper on CGs, John F. Sowa (Sowa 1976) used them to represent the conceptual schemas used in database systems. The first book on CGs (Sowa 1984) applied… … Wikipedia
Median graph — The median of three vertices in a median graph In mathematics, and more specifically graph theory, a median graph is an undirected graph in which any three vertices a, b, and c have a unique median: a vertex m(a,b,c) that belongs to shortest… … Wikipedia
List of graph theory topics — This is a list of graph theory topics, by Wikipedia page. See glossary of graph theory for basic terminology Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 … Wikipedia
Glossary of graph theory — Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with… … Wikipedia
Core (graph theory) — This article is about graph homomorphisms. For the subgraph in which all vertices have high degree, see k core. In the mathematical field of graph theory, a core is a notion that describes behavior of a graph with respect to graph homomorphisms.… … Wikipedia