Graph homomorphism

Imagine you have two sets of dots and lines.

You can map one set to the other. This must follow a rule. If two dots have a line, their new dots must have a line too.

This rule helps us solve puzzles. It can help us pick colors for shapes. We can use it to make a school schedule. It also helps us pick radio channels.

Some shapes are very special. We call these shapes a core. A core cannot be made smaller.

These shapes are very important in math.

Imagine you have two different graphs. A graph is a set of dots and lines. A graph homomorphism is a special way to link them.

This way must follow one strict rule. If two dots are joined by a line, their new dots must also have a line. This rule keeps the structure of the first graph. It respects how the dots are connected.

We use this idea to solve real problems. It can help us pick colors for a map. It also helps us make schedules. For example, you can use it to pick school classes. You can make sure no student has two classes at once.

Some graphs are very sturdy. We call these graphs a core. A core cannot be mapped to a smaller part of itself.

Every graph has its own unique core. This core is the simplest version of that graph. It is like the heart of the shape.

A graph homomorphism is a special way to map one graph to another. In math, a graph is a collection of dots called vertices and lines called edges. A homomorphism is a function that connects the dots of one graph to the dots of another. It must follow a very important rule to respect the original structure. If two dots are connected by a line in the first graph, their new dots must also be connected by a line in the second graph.

This rule ensures the mapping preserves the way the dots relate to each other.

This idea is closely linked to the way we color shapes. Imagine you have a graph and you want to give every dot a color. You must follow a rule where no two dots connected by a line have the same color. This is called a k-coloring if you use k different colors. Finding a k-coloring is actually the same thing as finding a homomorphism to a special graph called Kk. In this special graph, every dot is connected to every other dot.

Because all dots are connected, the mapping forces adjacent dots in your original graph to take different colors.

Some graphs have a very sturdy and simple heart called a core. A core is a graph that cannot be mapped into any smaller part of itself. Every single graph has its own unique core. You can think of the core as the most basic version of that graph's shape. For example, a complete graph like K7 is a core.

Another example is any cycle graph with an odd number of dots. If two graphs can map to each other, they are called homomorphically equivalent.

We can also use these mappings to solve tricky real-world puzzles. One example is making a school schedule for workshop courses. You can make a graph where each dot is a course. You draw a line between courses if a student takes both. Then, you map these to a second graph representing time slots. The second graph only has lines between slots that are far enough apart.

This ensures no student has two classes too close together in time.

Another use is helping wireless networks pick the right frequencies. Transmitters need to choose channels so they do not interfere with each other. You can make a graph of transmitters where lines connect those that are close together. Then, you map them to a graph of channels where lines connect frequencies that are far apart. This helps avoid signal interference. Finding these mappings can be a very hard job for computers. However, scientists study special cases to find faster ways to solve them.

In the mathematical field of graph theory, a graph homomorphism is a mapping between two graphs that respects their underlying structure. A graph is defined as a collection of vertices, or dots, and edges, or lines connecting them. A homomorphism is a specific type of function between the vertex sets of two graphs. The fundamental rule is that if two vertices are adjacent in the first graph, their mapped images must also be adjacent in the second graph.

This mapping ensures that the connectivity of the original graph is preserved within the target graph.

This concept can be applied to many different types of mathematical structures. While the standard definition involves finite, undirected graphs without multiple edges, it can be extended to directed graphs. In a directed graph, edges are called arcs and have a specific direction. For a homomorphism between directed graphs, if an arc exists from vertex $u$ to vertex $v$ in the first graph, then an arc must exist from their images in the second graph. There are also more specialized versions of these mappings. For example, a covering map is a surjective homomorphism that is also locally bijective. This means the mapping acts as a bijection on the neighborhood of each vertex.

Homomorphisms are deeply connected to the study of graph coloring. A $k$-coloring is an assignment of $k$ different colors to the vertices of a graph so that no two adjacent vertices share the same color. This process is exactly the same as finding a homomorphism from the graph to a complete graph, denoted as $K_k$. In a complete graph, every vertex is connected to every other vertex. Because of this, mapping to $K_k$ forces adjacent vertices in the original graph to land on different vertices in $K_k$, which represents different colors.

This relationship allows mathematicians to use the language of homomorphisms to study complex coloring problems, such as circular or fractional colorings.

Some graphs possess a fundamental, irreducible structure known as a core. A core is a graph that does not have a homomorphism to any of its proper subgraphs. This means the graph cannot be simplified or compressed into a smaller version of itself without losing its essential connectivity. Every graph is homomorphically equivalent to a unique core, which is the most basic version of that graph's structure. For instance, all complete graphs, such as $K_7$, are cores.

Similarly, any cycle graph with an odd number of vertices is also a core. If two graphs can map to each other through homomorphisms, they are considered homomorphically equivalent.

Beyond pure theory, homomorphisms serve as a powerful tool for solving constraint satisfaction problems (CSPs). These are problems where you must assign values to variables while following specific rules. One practical application is in scheduling workshop courses. If a student attends two different courses, those courses are connected by an edge in a graph. To ensure a student does not have classes too close together, one can map this graph to a second graph representing time slots. In this second graph, edges only connect slots that are sufficiently distant in time.

This ensures the resulting schedule respects the required time gaps.

Another useful application is in wireless network frequency allocation. Transmitters in a network must choose frequency channels that do not cause interference. By creating a graph where edges connect transmitters located geographically close to one another, engineers can model the problem. They then map this graph to a graph of available channels, where edges connect frequencies that are far apart. This mapping provides a valid way to assign channels so that nearby transmitters do not interfere with each other. While these models are simplified, they allow for complex adjustments, such as removing edges to account for specific geographical features or harmonic interference.

Finally, the study of homomorphisms connects to broader algebraic and computational fields. Because homomorphisms can be composed, they create rich structures such as preorders, distributive lattices, and categories. From a computational perspective, finding a homomorphism between two arbitrary graphs is often very difficult and time-consuming for computers. This is known as being computationally prohibitive. However, researchers actively study the boundaries between tractable cases, which are solvable in polynomial time, and intractable cases, which are much harder to solve. This ongoing research helps improve the algorithms used for various real-world optimization problems.