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.
Definitions In this article, unless stated otherwise, graphs are finite, undirected graphs with loops allowed, but multiple edges (parallel edges) disallowed. A graph homomorphismFor introductions, see (in order of increasing length): ; ; . from a graph to a graph , written , is a function from to that preserves edges. Formally,
implies , for all pairs of vertices in .
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 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 v0 and v1 and replacing each edge u,v with edges u0,v1 and v0,u1. The function mapping v0 and v1 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.
Cores and retracts
Two graphs G and H are homomorphically equivalent if G → H and H → G. The maps are not necessarily surjective nor injective. For instance, the complete bipartite graphs K2,2 and K3,3 are homomorphically equivalent: each map can be defined as taking the left (resp. right) half of the domain graph and mapping to just one vertex in the left (resp. right) half of the image graph.
A retraction is a homomorphism r from a graph G to a subgraph H of G such that r(v) = v for each vertex v of H. In this case the subgraph H is called a retract of G.
A core is a graph with no homomorphism to any proper subgraph. Equivalently, a core can be defined as a graph that does not retract to any proper subgraph. Every graph G is homomorphically equivalent to a unique core (up to isomorphism), called the core of G. Notably, this is not true in general for infinite graphs. However, the same definitions apply to directed graphs and a directed graph is also equivalent to a unique core. Every graph and every directed graph contains its core as a retract and as an induced subgraph.
For example, all complete graphs Kn and all odd cycles (cycle graphs of odd length) are cores. Every 3-colorable graph G that contains a triangle (that is, has the complete graph K3 as a subgraph) is homomorphically equivalent to K3. This is because, on one hand, a 3-coloring of G is the same as a homomorphism G → K3, as explained below. On the other hand, every subgraph of G trivially admits a homomorphism into G, implying K3 → G. This also means that K3 is the core of any such graph G. Similarly, every bipartite graph that has at least one edge is equivalent to K2.
Connection to colorings A k-coloring, for some integer k, is an assignment of one of k colors to each vertex of a graph G such that the endpoints of each edge get different colors. The k-colorings of G correspond exactly to homomorphisms from G to the complete graph Kk. Indeed, the vertices of Kk correspond to the k colors, and two colors are adjacent as vertices of Kk if and only if they are different. Hence a function defines a homomorphism to Kk if and only if it maps adjacent vertices of G to different colors (i.e., it is a k-coloring). In particular, G is k-colorable if and only if it is Kk-colorable.
If there are two homomorphisms G → H and H → Kk, then their composition G → Kk is also a homomorphism. In other words, if a graph H can be colored with k colors, and there is a homomorphism from G to H, then G can also be k-colored. Therefore, G → H implies χ(G) ≤ χ(H), where χ denotes the chromatic number of a graph (the least k for which it is k-colorable).
Variants General homomorphisms can also be thought of as a kind of coloring: if the vertices of a fixed graph H are the available colors and edges of H describe which colors are compatible, then an H-coloring of G is an assignment of colors to vertices of G such that adjacent vertices get compatible colors. Many notions of graph coloring fit into this pattern and can be expressed as graph homomorphisms into different families of graphs. Circular colorings can be defined using homomorphisms into circular complete graphs, refining the usual notion of colorings. Fractional and b-fold coloring can be defined using homomorphisms into Kneser graphs. T-colorings correspond to homomorphisms into certain infinite graphs. An oriented coloring of a directed graph is a homomorphism into any oriented graph. An L(2,1)-coloring is a homomorphism into the complement of the path graph that is locally injective, meaning it is required to be injective on the neighbourhood of every vertex.
Orientations without long paths
Another interesting connection concerns orientations of graphs. An orientation of an undirected graph G is any directed graph obtained by choosing one of the two possible orientations for each edge. An example of an orientation of the complete graph Kk is the transitive tournament k with vertices 1,2,…,k and arcs from i to j whenever i < j. A homomorphism between orientations of graphs G and H yields a homomorphism between the undirected graphs G and H, simply by disregarding the orientations. On the other hand, given a homomorphism G → H between undirected graphs, any orientation of H can be pulled back to an orientation of G so that has a homomorphism to . Therefore, a graph G is k-colorable (has a homomorphism to Kk) if and only if some orientation of G has a homomorphism to k.
A folklore theorem states that for all k, a directed graph G has a homomorphism to k if and only if it admits no homomorphism from the directed path k+1. Here n is the directed graph with vertices 1, 2, …, n and edges from i to i + 1, for i = 1, 2, …, n − 1. Therefore, a graph is k-colorable if and only if it has an orientation that admits no homomorphism from k+1. This statement can be strengthened slightly to say that a graph is k-colorable if and only if some orientation contains no directed path of length k (no k+1 as a subgraph). This is the Gallai–Hasse–Roy–Vitaver theorem.
Connection to constraint satisfaction problems Examples
Some scheduling problems can be modeled as a question about finding graph homomorphisms. As an example, one might want to assign workshop courses to time slots in a calendar so that two courses attended by the same student are not too close to each other in time. The courses form a graph G, with an edge between any two courses that are attended by some common student. The time slots form a graph H, with an edge between any two slots that are distant enough in time. For instance, if one wants a cyclical, weekly schedule, such that each student gets their workshop courses on non-consecutive days, then H would be the complement graph of C7. A graph homomorphism from G to H is then a schedule assigning courses to time slots, as specified. To add a requirement saying that, e.g., no single student has courses on both Friday and Monday, it suffices to remove the corresponding edge from H.
A simple frequency allocation problem can be specified as follows: a number of transmitters in a wireless network must choose a frequency channel on which they will transmit data. To avoid interference, transmitters that are geographically close should use channels with frequencies that are far apart. If this condition is approximated with a single threshold to define 'geographically close' and 'far apart', then a valid channel choice again corresponds to a graph homomorphism. It should go from the graph of transmitters G, with edges between pairs that are geographically close, to the graph of channels H, with edges between channels that are far apart. While this model is rather simplified, it does admit some flexibility: transmitter pairs that are not close but could interfere because of geographical features can be added to the edges of G. Those that do not communicate at the same time can be removed from it. Similarly, channel pairs that are far apart but exhibit harmonic interference can be removed from the edge set of H.
In each case, these simplified models display many of the issues that have to be handled in practice. Constraint satisfaction problems, which generalize graph homomorphism problems, can express various additional types of conditions (such as individual preferences, or bounds on the number of coinciding assignments). This allows the models to be made more realistic and practical.
Formal view Graphs and directed graphs can be viewed as a special case of the far more general notion called relational structures (defined as a set with a tuple of relations on it). Directed graphs are structures with a single binary relation (adjacency) on the domain (the vertex set)., note relational structures are called relational systems there. Under this view, homomorphisms of such structures are exactly graph homomorphisms. In general, the question of finding a homomorphism from one relational structure to another is a constraint satisfaction problem (CSP). The case of graphs gives a concrete first step that helps to understand more complicated CSPs. Many algorithmic methods for finding graph homomorphisms, like backtracking, constraint propagation and local search, apply to all CSPs.
For graphs G and H, the question of whether G has a homomorphism to H corresponds to a CSP instance with only one kind of constraint, as follows. The variables are the vertices of G and the domain for each variable is the vertex set of H. An evaluation is a function that assigns to each variable an element of the domain, so a function f from V(G) to V(H). Each edge or arc (u,v) of G then corresponds to the constraint ((u,v), E(H)). This is a constraint expressing that the evaluation should map the arc (u,v) to a pair (f(u),f(v)) that is in the relation E(H), that is, to an arc of H. A solution to the CSP is an evaluation that respects all constraints, so it is exactly a homomorphism from G to H.
Structure of homomorphisms Compositions of homomorphisms are homomorphisms. In particular, the relation → on graphs is transitive (and reflexive, trivially), so it is a preorder on graphs. Let the equivalence class of a graph G under homomorphic equivalence be [G]. The equivalence class can also be represented by the unique core in [G].