In the mathematical field of graph theory, a graph homomorphism is a mapping between two graphs that respects their structure. More concretely, it is a function between the vertex sets of two graphs that maps adjacent vertices to adjacent vertices.

Homomorphisms generalize various notions of graph colorings and allow the expression of an important class of constraint satisfaction problems, such as certain scheduling or frequency assignment problems. The fact that homomorphisms can be composed leads to rich algebraic structures: a preorder on graphs, a distributive lattice, and a category (one for undirected graphs and one for directed graphs). The computational complexity of finding a homomorphism between given graphs is prohibitive in general, but a lot is known about special cases that are solvable in polynomial time. Boundaries between tractable and intractable cases have been an active area of research.

In this article, unless stated otherwise, graphs are finite, undirected graphs with loops allowed, but multiple edges (parallel edges) disallowed. A graph homomorphism f  from a graph ${\displaystyle G=(V(G),E(G))}$ to a graph ${\displaystyle H=(V(H),E(H))}$, written

is a function from ${\displaystyle V(G)}$ to ${\displaystyle V(H)}$ that preserves edges. Formally, ${\displaystyle (u,v)\in E(G)}$ implies ${\displaystyle (f(u),f(v))\in E(H)}$, for all pairs of vertices ${\displaystyle u,v}$ in ${\displaystyle V(G)}$. If there exists any homomorphism from G to H, then G is said to be homomorphic to H or H-colorable. This is often denoted as just

The above definition is extended to directed graphs. Then, for a homomorphism f : G → H, (f(u),f(v)) is an arc (directed edge) of H whenever (u,v) is an arc of G.

There is an injective homomorphism from G to H (i.e., one that maps distinct vertices in G to distinct vertices in H) if and only if G is isomorphic to a subgraph of H. If a homomorphism f : G → H is a bijection, and its inverse function f⁻¹ is also a graph homomorphism, then f is a graph isomorphism.

Covering maps are a special kind of homomorphisms that mirror the definition and many properties of covering maps in topology. They are defined as surjective homomorphisms (i.e., something maps to each vertex) that are also locally bijective, that is, a bijection on the neighbourhood of each vertex. An example is the bipartite double cover, formed from a graph by splitting each vertex v into v₀ and v₁ and replacing each edge u,v with edges u₀,v₁ and v₀,u₁. The function mapping v₀ and v₁ in the cover to v in the original graph is a homomorphism and a covering map.

Graph homeomorphism is a different notion, not related directly to homomorphisms. Roughly speaking, it requires injectivity, but allows mapping edges to paths (not just to edges). Graph minors are a still more relaxed notion.