Editing Graph homomorphism (section)

==Definitions==
In this article, unless stated otherwise, ''graphs'' are finite, [[Graph (discrete mathematics)#Undirected graph|undirected graphs]] with [[Loop (graph theory)|loops]] allowed, but [[multiple edges]] (parallel edges) disallowed.
A '''graph homomorphism'''<ref name="intros">For introductions, see (in order of increasing length): {{harvtxt|Cameron|2006}}; {{harvtxt|Hahn|Tardif|1997}}; {{harvtxt|Hell|Nešetřil|2004}}.</ref>  {{math|''f''}}&nbsp; from a graph <math>G = (V(G), E(G))</math> to a graph <math> H = (V(H), E(H))</math>, written
: {{math|''f'' : ''G'' → ''H''}}
is a function from <math>V(G)</math> to <math>V(H)</math> that preserves edges. Formally, <math>(u,v) \in E(G)</math> implies <math>(f(u),f(v)) \in E(H)</math>, for all pairs of vertices <math>u, v</math> in <math>V(G)</math>.
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
: {{math|''G'' → ''H'' .}}

The above definition is extended to directed graphs. Then, for a homomorphism ''f'' : ''G'' → ''H'', (''f''(''u''),''f''(''v'')) is an [[directed edge|arc]] (directed edge) of ''H'' whenever (''u'',''v'') is an arc of ''G''.

There is an [[Injective function|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 [[Graph isomorphism|isomorphic]] to a [[Glossary of graph theory terms#subgraph|subgraph]] of ''H''.
If a homomorphism ''f'' : ''G'' → ''H'' is a [[bijection]], and its [[inverse function]] {{math|''f''<sup> −1</sup>}} is also a graph homomorphism, then ''f'' is a graph isomorphism.{{sfn|Hahn|Tardif|1997|loc=Observation 2.3}}

[[Covering graph|Covering maps]] are a special kind of homomorphisms that mirror the definition and many properties of [[Covering map|covering maps in topology]].{{sfn|Godsil|Royle|2001|p=115}}
They are defined as [[Surjective function|surjective]] homomorphisms (i.e., something maps to each vertex) that are also locally bijective, that is, a bijection on the [[neighbourhood (graph theory)|neighbourhood]] of each vertex.
An example is the [[bipartite double cover]], formed from a graph by splitting each vertex ''v'' into ''v<sub>0</sub>'' and ''v<sub>1</sub>'' and replacing each edge ''u'',''v'' with edges ''u<sub>0</sub>'',''v<sub>1</sub>'' and ''v<sub>0</sub>'',''u<sub>1</sub>''. The function mapping ''v<sub>0</sub>'' and ''v<sub>1</sub>'' in the cover to ''v'' in the original graph is a homomorphism and a covering map.

Graph [[Homeomorphism (graph theory)|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 minor]]s are a still more relaxed notion.

===Cores and retracts===
[[File:Complete graph K7.svg|thumb|upright=0.8|right|''K''<sub>7</sub>, the complete graph with 7 vertices, is a core.]]
{{main|Core (graph theory)}}

Two graphs ''G'' and ''H'' are '''homomorphically equivalent''' if
''G'' → ''H'' and ''H'' → ''G''.<ref name="intros" /> The maps are not necessarily surjective nor injective. For instance, the [[complete bipartite graph]]s ''K''<sub>2,2</sub> and ''K''<sub>3,3</sub> 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 [[Glossary of graph theory#Subgraphs|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''.{{sfn|Hell|Nešetřil|2004|p=19}}

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.{{sfn|Hell|Nešetřil|2004|loc=Proposition 1.31}}
Every graph ''G'' is homomorphically equivalent to a unique core (up to isomorphism), called ''the core'' of ''G''.{{sfnm|1a1=Cameron|1y=2006|1loc=Proposition 2.3|2a1=Hell|2a2=Nešetřil|2y=2004|2loc=Corollary 1.32}} Notably, this is not true in general for infinite graphs.{{sfn|Hell|Nešetřil|2004|p=34}}
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]].{{sfn|Hell|Nešetřil|2004|p=19}}

For example, all [[complete graph]]s ''K''<sub>n</sub> and all odd cycles ([[cycle graph]]s of odd length) are cores.
Every [[graph coloring#vertex coloring|3-colorable]] graph ''G'' that contains a triangle (that is, has the [[complete graph]] ''K''<sub>3</sub> as a subgraph) is homomorphically equivalent to ''K''<sub>3</sub>. This is because, on one hand, a 3-coloring of ''G'' is the same as a homomorphism ''G'' → ''K''<sub>3</sub>, as explained below. On the other hand, every subgraph of ''G'' trivially admits a homomorphism into ''G'', implying ''K''<sub>3</sub> → ''G''. This also means that ''K''<sub>3</sub> is the core of any such graph ''G''. Similarly, every [[bipartite graph]] that has at least one edge is equivalent to ''K''<sub>2</sub>.{{sfn|Cameron|2006|loc=Proposition 2.5|p=4}}