Graph homomorphism

A map from the vertices of one graph to another that sends every adjacent pair to an adjacent pair. It preserves edges but need not preserve nonedges or distinguish vertices.

Graph: A structure consisting of vertices and edges that connect pairs of vertices. Its vertices and edges are the domain and target of every graph homomorphism.
Composition of functions: The operation of applying one function to the output of another. Composing two graph homomorphisms always produces another homomorphism.
Graph homomorphism problem: The decision problem of determining whether a homomorphism exists between two given graphs. Its complexity varies sharply with the fixed target graph.
Induced subgraph: A subgraph containing every edge of the original graph whose endpoints both lie in the chosen vertex set. An induced embedding preserves both adjacency and nonadjacency, unlike a general homomorphism.
Graph coloring: An assignment of colors to graph vertices, often required to give adjacent vertices different colors. A proper coloring is exactly a homomorphism to a complete graph.
Constraint satisfaction problem: A problem asking for variable assignments that satisfy specified relations among variables. Finding a homomorphism is a constraint satisfaction problem with vertices as variables and edges as constraints.
Chromatic number: The minimum number of colors needed to color a graph so adjacent vertices receive different colors. It is the smallest size of a complete graph receiving a homomorphism from the graph.
Graph embedding: An injective representation of one graph inside another that preserves the relevant graph structure. Injectivity prevents the vertex identifications allowed by homomorphisms.
Complete graph: A graph in which every pair of distinct vertices is joined by an edge. Maps to complete graphs encode proper colorings of the source.
Adjacency matrix: A matrix recording which pairs of graph vertices are adjacent. The homomorphism condition can be checked by testing every source edge against target adjacency.

Linked from 5 pages