Graph homomorphism
Encyclopedia
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.
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.
Graph homomorphism preserves connectedness.
The tensor product of graphs
is the category-theoretic product
for the category of graphs and graph homomorphisms.
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
Kk: the vertices of Kk correspond to the colors of G, and f maps each vertex of G with color c to the vertex of Kk that corresponds to c. This is a valid homomorphism because the endpoints of each edge of G are mapped to distinct vertices of Kk, and every two distinct vertices of Kk are connected by an edge, so every edge in G is mapped to an adjacent pair of vertices in Kk. Conversely if f is a homomorphism from G to Kk, 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 Kk. Because Kk 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 Kk, so this gives a valid coloring. That is, G has a k-coloring if and only if it has a homomorphism to Kk.
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 k-colored. 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
Cg 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.
, i.e. deciding whether there exists a homomorphism from one graph to another, is NP-complete
.
Determining whether there is an isomorphism between two graphs is also an important problem in computational complexity theory; see graph isomorphism problem
.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
field of graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
a graph homomorphism is a mapping between two graphs
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
that respects their structure. More concretely it maps adjacent vertices
Vertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
to adjacent vertices.
Definitions
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 bijectionBijection
A bijection is a function giving an exact pairing of the elements of two sets. A bijection from the set X to the set Y has an inverse function from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements...
whose inverse function
Inverse function
In mathematics, an inverse function is a function that undoes another function: If an input x into the function ƒ produces an output y, then putting y into the inverse function g produces the output x, and vice versa. i.e., ƒ=y, and g=x...
is also a graph homomorphism, then
is a graph isomorphismGraph isomorphism
In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H f \colon V \to V \,\!such that any two vertices u and v of G are adjacent in G if and only if ƒ and ƒ are adjacent in H...
.
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.Properties
The composition of homomorphisms are homomorphisms.Graph homomorphism preserves connectedness.
The tensor product of graphs
Tensor product of graphs
In graph theory, the tensor product G × H of graphs G and H is a graph such that* the vertex set of G × H is the Cartesian product V × V; and...
is the category-theoretic product
Product (category theory)
In category theory, the product of two objects in a category is a notion designed to capture the essence behind constructions in other areas of mathematics such as the cartesian product of sets, the direct product of groups, the direct product of rings and the product of topological spaces...
for the category of graphs and graph homomorphisms.
Connection to coloring and girth
A graph coloringGraph coloring
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 subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
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 graphComplete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
Kk: the vertices of Kk correspond to the colors of G, and f maps each vertex of G with color c to the vertex of Kk that corresponds to c. This is a valid homomorphism because the endpoints of each edge of G are mapped to distinct vertices of Kk, and every two distinct vertices of Kk are connected by an edge, so every edge in G is mapped to an adjacent pair of vertices in Kk. Conversely if f is a homomorphism from G to Kk, 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 Kk. Because Kk 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 Kk, so this gives a valid coloring. That is, G has a k-coloring if and only if it has a homomorphism to Kk.
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 k-colored. 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
Cycle graph
In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called Cn...
Cg 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 problemDecision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
, i.e. deciding whether there exists a homomorphism from one graph to another, is NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
.
Determining whether there is an isomorphism between two graphs is also an important problem in computational complexity theory; see graph isomorphism problem
Graph isomorphism problem
The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.Besides its practical importance, the graph isomorphism problem is a curiosity in computational complexity theory as it is one of a very small number of problems belonging to NP...
.
See also
- Hadwiger's conjectureHadwiger conjecture (graph theory)In graph theory, the Hadwiger conjecture states that, if all proper colorings of an undirected graph G use k or more colors, then one can find k disjoint connected subgraphs of G such that each subgraph is connected by an edge to each other subgraph...
. - Graph rewritingGraph rewritingGraph transformation, or Graph rewriting, concerns the technique of creating a new graph out of an original graph using some automatic machine. It has numerous applications, ranging from software verification to layout algorithms....
- Median graphMedian graphIn 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 that belongs to shortest paths between any two of a, b, and c.The concept of median graphs has long been studied, for instance by or ...
s, definable as the retracts of hypercubes.