View source for 2–3 heap

{{Distinguish|graph homeomorphism}}
In the [[mathematics|mathematical]] field of [[graph theory]] a '''graph homomorphism''' is a mapping between two [[graph (mathematics)|graphs]] that respects their structure. More concretely it maps adjacent [[vertex (graph theory)|vertices]] to adjacent vertices.

==Definitions==
A '''graph homomorphism''' <math>f</math> from a graph <math>G=(V,E)</math> to a graph <math>G'=(V',E')</math>, written <math>f:G \rightarrow G'</math>, is a mapping
<math>f:V \rightarrow V'</math> from the vertex set of <math>G</math> to the vertex set of <math>G'</math> such that <math>\{u,v\}\in E</math> implies <math>\{f(u),f(v)\}\in E'</math>.  

The above definition is extended to directed graphs. Then, for a homomorphism <math>f:G \rightarrow G'</math>, <math>(f(u),f(v))</math> is an [[directed edge|arc]] of <math>G'</math> if <math>(u,v)</math> is an arc of <math>G</math>.

If there exists a homomorphism <math>f:G\rightarrow H</math> we shall write <math>G\rightarrow H</math>, and <math>G\not\rightarrow H</math> otherwise. If <math>G\rightarrow H</math>, <math>G</math> is said to be '''homomorphic''' to <math>H</math> or '''<math>H</math>-colourable'''.

If the homomorphism <math>f:G\rightarrow G'</math> is a [[bijection]] whose [[inverse function]] is also a graph homomorphism, then <math>f</math> is a [[graph isomorphism]]. 

Two graphs <math>G</math> and <math>G'</math> are '''homomorphically equivalent''' if
<math>G\rightarrow G'</math> and <math>G'\rightarrow G</math>.

A '''retract''' of a graph <math>G</math> is a [[Glossary of graph theory#Subgraphs|subgraph]] <math>H</math> of <math>G</math> such that there exists a homomorphism <math>r:G\rightarrow H</math>, called '''retraction''' with <math>r(x)=x</math> for any vertex <math>x</math> of <math>H</math>. A '''core''' is a graph which does not retract to a proper subgraph. Any graph is homomorphically equivalent to a unique core.

==Properties==
The composition of homomorphisms are homomorphisms.

Graph homomorphism preserves [[connectedness (graph theory)|connectedness]].

The [[tensor product of graphs]] is the [[Product (category theory)|category-theoretic product]] for the category of graphs and graph homomorphisms.

==Connection to coloring and girth==
A [[graph coloring]] is an assignment of one of ''k'' colors to a graph ''G'' so that the endpoints of each edge have different colors, for some number ''k''.  Any coloring corresponds to a homomorphism <math>f:G\rightarrow K_k</math> from ''G'' to a [[complete graph]] ''K''<sub>''k''</sub>: the vertices of ''K''<sub>''k''</sub> correspond to the colors of ''G'', and ''f'' maps each vertex of ''G'' with color ''c'' to the vertex of ''K''<sub>''k''</sub> that corresponds to&nbsp;''c''. This is a valid homomorphism because the endpoints of each edge of ''G'' are mapped to distinct vertices of ''K''<sub>''k''</sub>, and every two distinct vertices of ''K''<sub>''k''</sub> are connected by an edge, so every edge in ''G'' is mapped to an adjacent pair of vertices in ''K''<sub>''k''</sub>. Conversely if ''f'' is a homomorphism from ''G'' to ''K''<sub>''k''</sub>, then one can color ''G'' by using the same color for two vertices in ''G'' whenever they are both mapped to the same vertex in ''K''<sub>''k''</sub>. Because ''K''<sub>''k''</sub> has no edges that connect a vertex to itself, it is not possible for two adjacent vertices in ''G'' to both be mapped to the same vertex in ''K''<sub>''k''</sub>, so this gives a valid coloring. That is, ''G'' has a ''k''-coloring if and only if it has a homomorphism to ''K''<sub>''k''</sub>.

If there are two homomorphisms <math>H\rightarrow G\rightarrow K_k</math>, then their composition <math>H\rightarrow K_k</math> is also a homomorphism. In other words, if a graph ''G'' can be colored with ''k'' colors, and there is a homomorphism <math>H\rightarrow G</math>, then ''H'' can also be ''k''-colored. Therefore, whenever a homomorphism <math>H\rightarrow G</math> exists, the [[chromatic number]] of ''H'' is less than or equal to the chromatic number of ''G''.

Homomorphisms can also be used very similarly to characterize the [[Girth (graph theory)|odd girth]] of a graph ''G'', the length of its shortest odd-length cycle.
The odd girth is, equivalently, the smallest [[odd number]] ''g'' for which there exists a homomorphism <math>C_g\rightarrow G</math>. For this reason, if <math>G\rightarrow H</math>, then the odd girth of ''G'' is greater than or equal to the corresponding invariant of ''H''.<ref>{{harvtxt|Hell|Nešetřil|2004}}, p. 7.</ref>

==Complexity==
The associated [[decision problem]], i.e. deciding whether there exists a homomorphism from one graph to another, is [[NP-complete]].
Determining whether there is an isomorphism between two graphs is also an important problem in computational complexity theory; see [[graph isomorphism problem]].

== See also ==
* [[Hadwiger conjecture (graph theory)|Hadwiger's conjecture]].
* [[Graph rewriting]]
* [[Median graph]]s, definable as the retracts of [[hypercube graph|hypercube]]s.

==Notes==
{{reflist}}

== References ==
* {{citation |last=Hell |first=Pavol |author2-link= Jaroslav Nešetřil|last2=Nešetřil | first2=Jaroslav |publisher=Oxford University Press |title=Graphs and Homomorphisms (Oxford Lecture Series in Mathematics and Its Applications)|year=2004 |isbn=0-19-852817-5}}
*{{citation|last=Mitchell|first=James D.|title=Endomorphism monoids of all connected graphs with at most 7 vertices|url=http://www-groups.mcs.st-andrews.ac.uk/~jamesm/graphs/index.php|year=2011}}.

* R. Brown, I. Morris, J. Shrimpton and C.D. Wensley, `Graphs of Morphisms of Graphs',  Electronic Journal of Combinatorics, A1 of Volume 15(1), 2008. 1-28.

[[Category:Graph theory]]
[[Category:Morphisms]]