Editing Graph homomorphism (section)

{{Short description|Structure-preserving correspondence between node-link graphs}}
{{Distinguish|graph homeomorphism}}
{{good article}}
[[File:Graph homomorphism into C5.svg|upright=1.2|thumb|alt= Graph homomorphism from J5 into C5|A homomorphism from the [[flower snark]] ''J''<sub>5</sub> into the cycle graph ''C''<sub>5</sub>.<br/>It is also a retraction onto the subgraph on the central five vertices. Thus ''J''<sub>5</sub> is in fact {{shy|homo|mor|phi|cally}} equivalent to the [[core (graph theory)|core]] ''C''<sub>5</sub>.]]
In the [[mathematics|mathematical]] field of [[graph theory]], a '''graph homomorphism''' is a mapping between two [[graph (discrete mathematics)|graph]]s that respects their structure. More concretely, it is a function between the vertex sets of two graphs that maps adjacent [[vertex (graph theory)|vertices]] to adjacent vertices.

Homomorphisms generalize various notions of [[graph coloring]]s and allow the expression of an important class of [[constraint satisfaction problem]]s, such as certain [[Scheduling (production processes)|scheduling]] or [[frequency assignment]] problems.{{sfn|Hell|Nešetřil|2004|p=27}}
The fact that homomorphisms can be composed leads to rich algebraic structures: a [[preorder]] on graphs, a [[distributive lattice]], and a [[category (mathematics)|category]] (one for undirected graphs and one for directed graphs).{{sfn|Hell|Nešetřil|2004|p=109}}
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 [[Time complexity#Polynomial time|polynomial time]]. Boundaries between tractable and intractable cases have been an active area of research.{{sfn|Hell|Nešetřil|2008}}