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.
A graph homomorphism
f
from a graph
G
=
(
V
,
E
)
to a graph
G
′
=
(
V
′
,
E
′
)
, written
f
:
G
→
G
′
, is a mapping
f
:
V
→
V
′
from the vertex set of
G
to the vertex set of
G
′
such that
{
u
,
v
}
∈
E
implies
{
f
(
u
)
,
f
(
v
)
}
∈
E
′
.
The above definition is extended to directed graphs. Then, for a homomorphism
f
:
G
→
G
′
,
(
f
(
u
)
,
f
(
v
)
)
is an arc of
G
′
if
(
u
,
v
)
is an arc of
G
.
If there exists a homomorphism
f
:
G
→
H
we shall write
G
→
H
, and
G
↛
H
otherwise. If
G
→
H
,
G
is said to be homomorphic to
H
or
H
-colourable.
If the homomorphism
f
:
G
→
G
′
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
G
→
G
′
and
G
′
→
G
.
A retract of a graph
G
is a subgraph
H
of
G
such that there exists a homomorphism
r
:
G
→
H
, 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.
The composition of homomorphisms are homomorphisms.
Graph homomorphism preserves connectedness.
The tensor product of graphs is the category-theoretic 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 each vertex of a graph G so that the endpoints of each edge have different colors, for some number k. Any coloring corresponds to a homomorphism
f
:
G
→
K
k
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
H
→
G
→
K
k
, then their composition
H
→
K
k
is also a homomorphism. In other words, if a graph G can be colored with k colors, and there is a homomorphism
H
→
G
, then H can also be k-colored. Therefore, whenever a homomorphism
H
→
G
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 odd girth of a graph G, the length of its shortest odd-length cycle. The odd girth is, equivalently, the smallest odd number g for which there exists a homomorphism
C
g
→
G
. For this reason, if
G
→
H
, then the odd girth of G is greater than or equal to the corresponding invariant of H.
The associated decision problem, 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.