Editing Graph homomorphism

{{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}}

==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}}

==Connection to colorings==
A [[graph coloring|''k''-coloring]], for some integer ''k'', is an assignment of one of ''k'' colors to each vertex of a graph ''G'' such that the endpoints of each edge get different colors. The ''k''-colorings of ''G'' correspond exactly to homomorphisms from ''G'' to the [[complete graph]] ''K''<sub>''k''</sub>.{{sfnm|1a1=Cameron|1y=2006|1p=1|2a1=Hell|2a2=Nešetřil|2y=2004|2loc=Proposition 1.7}} Indeed, the vertices of ''K''<sub>''k''</sub> correspond to the ''k'' colors, and two colors are adjacent as vertices of ''K''<sub>''k''</sub> if and only if they are different. Hence a function defines a homomorphism to ''K''<sub>''k''</sub> if and only if it maps adjacent vertices of ''G'' to different colors (i.e., it is a ''k''-coloring). In particular, ''G'' is ''k''-colorable if and only if it is ''K''<sub>''k''</sub>-colorable.{{sfnm|1a1=Cameron|1y=2006|1p=1|2a1=Hell|2a2=Nešetřil|2y=2004|2loc=Proposition 1.7}}

If there are two homomorphisms ''G'' → ''H'' and ''H'' → ''K''<sub>''k''</sub>, then their composition ''G'' → ''K''<sub>''k''</sub> is also a homomorphism.{{sfn|Hell|Nešetřil|2004|loc=§1.7}} In other words, if a graph ''H'' can be colored with ''k'' colors, and there is a homomorphism from ''G'' to ''H'', then ''G'' can also be ''k''-colored. Therefore, ''G'' → ''H'' implies χ(''G'') ≤  χ(''H''), where ''χ'' denotes the [[chromatic number]] of a graph (the least ''k'' for which it is ''k''-colorable).{{sfn|Hell|Nešetřil|2004|loc=Corollary 1.8}}

===Variants===
General homomorphisms can also be thought of as a kind of coloring: if the vertices of a fixed graph ''H'' are the available ''colors'' and edges of ''H'' describe which colors are ''compatible'', then an ''H''-coloring of ''G'' is an assignment of colors to vertices of ''G'' such that adjacent vertices get compatible colors.
Many notions of graph coloring fit into this pattern and can be expressed as graph homomorphisms into different families of graphs.
[[Circular coloring]]s can be defined using homomorphisms into [[circular clique|circular complete graph]]s, refining the usual notion of colorings.{{sfnm|1a1=Hell|1a2=Nešetřil|1y=2004|1loc=§6.1|2a1=Hahn|2a2=Tardif|2y=1997|2loc=§4.4}}
[[Fractional coloring|Fractional]] and [[Fractional coloring#Definitions|''b''-fold coloring]] can be defined using homomorphisms into [[Kneser graph]]s.{{sfnm|1a1=Hell|1a2=Nešetřil|1y=2004|1loc=§6.2|2a1=Hahn|2a2=Tardif|2y=1997|2loc=§4.5}}
[[T-coloring]]s correspond to homomorphisms into certain infinite graphs.{{sfn|Hell|Nešetřil|2004|loc=§6.3}}
An [[oriented coloring]] of a directed graph is a homomorphism into any [[oriented graph]].{{sfn|Hell|Nešetřil|2004|loc=§6.4}}
An [[L(2,1)-coloring]] is a homomorphism into the [[complement graph|complement]] of the [[path graph]] that is locally injective, meaning it is required to be injective on the neighbourhood of every vertex.<ref>{{citation|first1=J.|last1=Fiala|first2=J.|author2-link=Jan Kratochvíl|last2=Kratochvíl|s2cid=17507393|title=Partial covers of graphs|year=2002|journal=Discussiones Mathematicae Graph Theory|volume=22|issue=1|pages=89–99|doi=10.7151/dmgt.1159}}</ref>

===Orientations without long paths===
{{main|Gallai–Hasse–Roy–Vitaver theorem}}
Another interesting connection concerns [[Orientation (graph theory)|orientations]] of graphs.
An orientation of an undirected graph ''G'' is any directed graph obtained by choosing one of the two possible orientations for each edge.
An example of an orientation of the complete graph ''K<sub>k</sub>'' is the transitive tournament {{vec|{{var|T}}}}<sub>''k''</sub> with vertices 1,2,…,''k'' and arcs from ''i'' to ''j'' whenever ''i'' < ''j''.
A homomorphism between orientations of graphs ''G'' and ''H'' yields a homomorphism between the undirected graphs ''G'' and ''H'', simply by disregarding the orientations.
On the other hand, given a homomorphism ''G'' → ''H'' between undirected graphs, any orientation {{vec|{{var|H}}}} of ''H'' can be pulled back to an orientation {{vec|{{var|G}}}} of ''G'' so that {{vec|{{var|G}}}} has a homomorphism to {{vec|{{var|H}}}}.
Therefore, a graph ''G'' is ''k''-colorable (has a homomorphism to ''K<sub>k</sub>'') if and only if some orientation of ''G'' has a homomorphism to {{vec|{{var|T}}}}<sub>''k''</sub>.{{sfn|Hell|Nešetřil|2004|pp=13–14}}

A folklore theorem states that for all ''k'', a directed graph ''G'' has a homomorphism to {{vec|{{var|T}}}}<sub>''k''</sub> if and only if it admits no homomorphism from the directed path {{vec|{{var|P}}}}<sub>''k''+1</sub>.{{sfn|Hell|Nešetřil|2004|loc=Proposition 1.20}}
Here {{vec|{{var|P}}}}<sub>''n''</sub> is the directed graph with vertices 1, 2, …, ''n'' and edges from ''i'' to ''i'' + 1, for ''i'' = 1, 2, …, ''n'' − 1.
Therefore, a graph is ''k''-colorable if and only if it has an orientation that admits no homomorphism from {{vec|{{var|P}}}}<sub>''k''+1</sub>.
This statement can be strengthened slightly to say that a graph is ''k''-colorable if and only if some orientation contains no directed path of length ''k'' (no {{vec|{{var|P}}}}<sub>''k''+1</sub> as a subgraph). 
This is the [[Gallai–Hasse–Roy–Vitaver theorem]].

==Connection to constraint satisfaction problems==
===Examples===
[[File:Graph of non-adjacent weekdays.svg|thumb|Graph ''H'' of non-consecutive weekdays, isomorphic to the [[complement graph]] of ''C''<sub>7</sub> and to the [[circular clique]] ''K''<sub>7/2</sub>]]
Some scheduling problems can be modeled as a question about finding graph homomorphisms.{{sfn|Cameron|2006|p=1}}{{sfn|Hell|Nešetřil|2004|loc=§1.8}} As an example, one might want to assign workshop courses to time slots in a calendar so that two courses attended by the same student are not too close to each other in time. The courses form a graph ''G'', with an edge between any two courses that are attended by some common student. The time slots form a graph ''H'', with an edge between any two slots that are distant enough in time. For instance, if one wants a cyclical, weekly schedule, such that each student gets their workshop courses on non-consecutive days, then ''H'' would be the [[complement graph]] of ''C''<sub>7</sub>. A graph homomorphism from ''G'' to ''H'' is then a schedule assigning courses to time slots, as specified.{{sfn|Cameron|2006|p=1}} To add a requirement saying that, e.g., no single student has courses on both Friday and Monday, it suffices to remove the corresponding edge from ''H''.

A simple [[frequency allocation]] problem can be specified as follows: a number of transmitters in a [[wireless network]] must choose a frequency channel on which they will transmit data. To avoid [[Electromagnetic interference|interference]], transmitters that are geographically close should use channels with frequencies that are far apart. If this condition is approximated with a single threshold to define 'geographically close' and 'far apart', then a valid channel choice again corresponds to a graph homomorphism. It should go from the graph of transmitters ''G'', with edges between pairs that are geographically close, to the graph of channels ''H'', with edges between channels that are far apart. While this model is rather simplified, it does admit some flexibility: transmitter pairs that are not close but could interfere because of geographical features can be added to the edges of ''G''. Those that do not communicate at the same time can be removed from it. Similarly, channel pairs that are far apart but exhibit [[harmonic]] interference can be removed from the edge set of ''H''.{{sfn|Hell|Nešetřil|2004|pp=30–31}}

In each case, these simplified models display many of the issues that have to be handled in practice.{{sfn|Hell|Nešetřil|2004|pp=31–32}} [[Constraint satisfaction problem]]s, which generalize graph homomorphism problems, can express various additional types of conditions (such as individual preferences, or bounds on the number of coinciding assignments). This allows the models to be made more realistic and practical.

===Formal view===
Graphs and directed graphs can be viewed as a special case of the far more general notion called relational [[Structure (mathematical logic)|structure]]s (defined as a set with a tuple of relations on it). Directed graphs are structures with a single binary relation (adjacency) on the domain (the vertex set).<ref name="HN-csp">{{harvnb|Hell|Nešetřil|2004|p=28}}, note ''relational structures'' are called ''relational systems'' there.</ref>{{sfn|Hell|Nešetřil|2008}} Under this view, [[Structure (mathematical logic)#Homomorphisms|homomorphisms]] of such structures are exactly graph homomorphisms.
In general, the question of finding a homomorphism from one relational structure to another is a [[constraint satisfaction problem]] (CSP).
The case of graphs gives a concrete first step that helps to understand more complicated CSPs.
Many algorithmic methods for finding graph homomorphisms, like [[backtracking]], [[constraint propagation]] and [[Local search (constraint satisfaction)|local search]], apply to all CSPs.{{sfn|Hell|Nešetřil|2008}}

For graphs ''G'' and ''H'', the question of whether ''G'' has a homomorphism to ''H'' corresponds to a CSP instance with only one kind of constraint,{{sfn|Hell|Nešetřil|2008}} as follows. The ''variables'' are the vertices of ''G'' and the ''domain'' for each variable is the vertex set of ''H''. An ''evaluation'' is a function that assigns to each variable an element of the domain, so a function ''f'' from ''V''(''G'') to ''V''(''H''). Each edge or arc (''u'',''v'') of ''G'' then corresponds to the ''constraint'' ((''u'',''v''), E(''H'')). This is a constraint expressing that the evaluation should map the arc (''u'',''v'') to a pair (''f''(''u''),''f''(''v'')) that is in the relation ''E''(''H''), that is, to an arc of ''H''. A solution to the CSP is an evaluation that respects all constraints, so it is exactly a homomorphism from ''G'' to ''H''.

==Structure of homomorphisms==
Compositions of homomorphisms are homomorphisms.{{sfn|Hell|Nešetřil|2004|loc=§1.7}} 
In particular, the relation → on graphs is transitive (and reflexive, trivially), so it is a [[preorder]] on graphs.{{sfn|Hell|Nešetřil|2004|loc=§3.1}}
Let the [[equivalence class]] of a graph ''G'' under [[homomorphic equivalence]] be [''G''].
The equivalence class can also be represented by the unique core in [''G''].
The relation → is a [[partial order]] on those equivalence classes; it defines a [[poset]].{{sfn|Hell|Nešetřil|2004|loc=Theorem 3.1}}

Let ''G'' < ''H'' denote that there is a homomorphism from ''G'' to ''H'', but no homomorphism from ''H'' to ''G''.
The relation → is a [[dense order]], meaning that for all (undirected) graphs ''G'', ''H'' such that ''G'' < ''H'', there is a graph ''K'' such that ''G'' < ''K'' < ''H'' (this holds except for the trivial cases ''G'' = ''K''<sub>0</sub> or ''K''<sub>1</sub>).{{sfnm|1a1=Hell|1a2=Nešetřil|1y=2004|1loc=Theorem 3.30|2a1=Hahn|2a2=Tardif|2y=1997|2loc=Theorem 2.33}}<ref>{{citation|first=E.|last=Welzl|title=Color-families are dense|year=1982|journal=[[Theoretical Computer Science (journal)|Theoretical Computer Science]]|volume=17|pages=29–41|doi=10.1016/0304-3975(82)90129-3|doi-access=free}}</ref>
For example, between any two [[complete graph]]s (except ''K''<sub>0</sub>, ''K''<sub>1</sub>, ''K''<sub>2</sub>) there are infinitely many [[circular clique|circular complete graphs]], corresponding to rational numbers between natural numbers.{{sfnm|1a1=Hell|1a2=Nešetřil|1y=2004|1p=192|2a1=Hahn|2a2=Tardif|2y=1997|2p=127}}

The poset of equivalence classes of graphs under homomorphisms is a [[distributive lattice]], with the [[Join and meet|join]] of  [''G''] and  [''H''] defined as (the equivalence class of) the disjoint union [''G'' ∪ ''H''], and the [[Join and meet|meet]] of [''G''] and  [''H''] defined as the [[tensor product of graphs|tensor product]] [''G'' × ''H''] (the choice of graphs ''G'' and ''H'' representing the equivalence classes [''G''] and [''H''] does not matter).<ref>{{harvnb|Hell|Nešetřil|2004|loc=Proposition 3.2}}, distributivity is stated in Proposition 2.4; {{harvnb|Hahn|Tardif|1997|loc=Theorem 2.37}}.</ref>
The [[join-irreducible]] elements of this lattice are exactly [[Connectivity (graph theory)|connected]] graphs. This can be shown using the fact that a homomorphism maps a connected graph into one connected component of the target graph.<ref>{{citation
 | last1 = Kwuida | first1 = Léonard
 | last2 = Lehtonen | first2 = Erkko
 | title = On the Homomorphism Order of Labeled Posets
 | doi = 10.1007/s11083-010-9169-x
 | year = 2011
 | arxiv = 0911.0200
 | journal = [[Order (journal)|Order]]
 | volume = 28
 | issue = 2
 | pages = 251–265
 | s2cid = 14920600
 }}</ref>{{sfn|Gray|2014|loc=Lemma 3.7}}
The [[meet-irreducible]] elements of this lattice are exactly the [[Hedetniemi's conjecture#multiplicative graphs|multiplicative graphs]]. These are the graphs ''K'' such that a product ''G'' × ''H'' has a homomorphism to ''K'' only when one of ''G'' or ''H'' also does. Identifying multiplicative graphs lies at the heart of [[Hedetniemi's conjecture]].<ref>{{citation
 | last = Tardif
 | first = C.
 | title = Hedetniemi's conjecture, 40 years later
 | url = http://www.mast.queensu.ca/~ctardif/articles/gtn5406rp.pdf
 | pages = 46–57
 | volume = 54
 | journal = Graph Theory Notes of New York
 | mr = 2445666
 | year = 2008
 | access-date = 2017-08-05
 | archive-date = 2021-07-12
 | archive-url = https://web.archive.org/web/20210712104609/https://mast.queensu.ca/~ctardif/articles/gtn5406rp.pdf
 | url-status = dead
 }}.</ref><ref name="lattices">{{citation|first1=D.|last1=Duffus|first2=N.|last2=Sauer|title=Lattices arising in categorial investigations of Hedetniemi's conjecture|journal=[[Discrete Mathematics (journal)|Discrete Mathematics]]|volume=152|issue=1–3|year=1996|pages=125–139|doi=10.1016/0012-365X(94)00298-W|doi-access=free}}</ref>

Graph homomorphisms also form a [[category (mathematics)|category]], with graphs as objects and homomorphisms as arrows.{{sfn|Hell|Nešetřil|2004|p=125}}
The [[Initial and terminal objects|initial object]] is the empty graph, while the [[Initial and terminal objects|terminal object]] is the graph with one vertex and one [[Loop (graph theory)|loop]] at that vertex.
The [[tensor product of graphs]] is the [[Product (category theory)|category-theoretic product]] and 
the [[Hedetniemi's conjecture#Exponential graph|exponential graph]] is the [[exponential object]] for this category.<ref name="lattices"/>{{sfn|Gray|2014}}
Since these two operations are always defined, the category of graphs is a [[cartesian closed category]].
For the same reason, the lattice of equivalence classes of graphs under homomorphisms is in fact a [[Heyting algebra]].<ref name="lattices"/>{{sfn|Gray|2014}}

For directed graphs the same definitions apply. In particular → is a [[partial order]] on equivalence classes of directed graphs. It is distinct from the order → on equivalence classes of undirected graphs, but contains it as a suborder. This is because every undirected graph can be thought of as a directed graph where every arc (''u'',''v'') appears together with its inverse arc (''v'',''u''), and this does not change the definition of homomorphism. The order → for directed graphs is again a distributive lattice and a Heyting algebra, with join and meet operations defined as before. However, it is not dense. There is also a category with directed graphs as objects and homomorphisms as arrows, which is again a [[cartesian closed category]].{{sfn|Brown|Morris|Shrimpton|Wensley|2008}}{{sfn|Gray|2014}}

===Incomparable graphs===
[[File:Groetzsch-graph.svg|thumb|upright=0.8|right|The Grötzsch graph, incomparable to ''K''<sub>3</sub>]]
There are many incomparable graphs with respect to the homomorphism preorder, that is, pairs of graphs such that neither admits a homomorphism into the other.{{sfn|Hell|Nešetřil|2004|p=7}}
One way to construct them is to consider 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 from the [[cycle graph]] on ''g'' vertices to ''G''. For this reason, if ''G'' → ''H'', then the odd girth of ''G'' is greater than or equal to the odd girth of ''H''.{{sfn|Hahn|Tardif|1997|loc=Observation 2.6}}

On the other hand, if ''G'' → ''H'', then the chromatic number of ''G'' is less than or equal to the chromatic number of ''H''. 
Therefore, if ''G'' has strictly larger odd girth than ''H'' and strictly larger chromatic number than ''H'', then ''G'' and ''H'' are incomparable.{{sfn|Hell|Nešetřil|2004|p=7}}
For example, the [[Grötzsch graph]] is 4-chromatic and triangle-free (it has girth 4 and odd girth 5),<ref>{{mathworld | title = Grötzsch Graph | urlname = GroetzschGraph|mode=cs2}}</ref> so it is incomparable to the triangle graph ''K''<sub>3</sub>.

Examples of graphs with arbitrarily large values of odd girth and chromatic number are [[Kneser graph]]s{{sfn|Hahn|Tardif|1997|loc=Proposition 3.14}} and [[Mycielskian#Cones over graphs|generalized Mycielskians]].<ref>{{citation|
title=On Graphs With Strongly Independent Color-Classes|
first1=A.|last1=Gyárfás|first2=T.|last2=Jensen|first3=M.|last3=Stiebitz|
year=2004|doi=10.1002/jgt.10165|journal=[[Journal of Graph Theory]]|volume=46|issue=1|pages=1–14|
s2cid=17859655}}</ref>
A sequence of such graphs, with simultaneously increasing values of both parameters, gives infinitely many incomparable graphs (an [[antichain]] in the homomorphism preorder).{{sfn|Hell|Nešetřil|2004|loc=Proposition 3.4}}
Other properties, such as [[dense order|density]] of the homomorphism preorder, can be proved using such families.{{sfn|Hell|Nešetřil|2004|p=96}}
Constructions of graphs with large values of chromatic number and girth, not just odd girth, are also possible, but more complicated (see [[Girth (graph theory)#Girth and graph coloring|Girth and graph coloring]]).

Among directed graphs, it is much easier to find incomparable pairs. For example, consider the directed cycle graphs ''{{vec|C}}<sub>n</sub>'', with vertices 1, 2, …, ''n'' and edges from ''i'' to ''i'' + 1 (for ''i'' = 1, 2, …, ''n'' − 1) and from ''n'' to 1.
There is a homomorphism from ''{{vec|C}}<sub>n</sub>'' to ''{{vec|C}}<sub>k</sub>'' (''n'', ''k'' ≥ 3) if and only if ''n'' is a multiple of ''k''. 
In particular, directed cycle graphs ''{{vec|C}}<sub>n</sub>'' with ''n'' prime are all incomparable.{{sfn|Hell|Nešetřil|2004|p=35}}

==Computational complexity==
In the graph homomorphism problem, an instance is a pair of graphs (''G'',''H'') and a solution is a homomorphism from ''G'' to ''H''. The general [[decision problem]], asking whether there is any solution, is [[NP-complete]].{{sfn|Bodirsky|2007|loc=§1.3}} However, limiting allowed instances gives rise to a variety of different problems, some of which are much easier to solve. Methods that apply when restraining the left side  ''G'' are very different than for the right side ''H'', but in each case a dichotomy (a sharp boundary between easy and hard cases) is known or conjectured.

===Homomorphisms to a fixed graph===
The homomorphism problem with a fixed graph ''H'' on the right side of each instance is also called the ''H''-coloring problem. When ''H'' is the complete graph ''K''<sub>''k''</sub>, this is the [[Graph coloring#Computational complexity|graph ''k''-coloring problem]], which is solvable in polynomial time for ''k'' = 0, 1, 2, and [[NP-complete]] otherwise.{{sfn|Hell|Nešetřil|2004|loc=§5.1}}
In particular, ''K''<sub>2</sub>-colorability of a graph ''G'' is equivalent to ''G'' being [[Bipartite graph#Testing bipartiteness|bipartite]], which can be tested in linear time.
More generally, whenever ''H'' is a bipartite graph, ''H''-colorability is equivalent to ''K''<sub>2</sub>-colorability (or ''K''<sub>''0''</sub> / ''K''<sub>''1''</sub>-colorability when ''H'' is empty/edgeless), hence equally easy to decide.{{sfn|Hell|Nešetřil|2004|loc=Proposition 5.1}}
[[Pavol Hell]] and [[Jaroslav Nešetřil]] proved that, for undirected graphs, no other case is tractable:

: '''Hell–Nešetřil theorem''' (1990): The ''H''-coloring problem is in P when ''H'' is bipartite and NP-complete otherwise.{{sfn|Hell|Nešetřil|2004|loc=§5.2}}<ref>{{citation|first1=Pavol|last1=Hell|author1-link=Pavol Hell|first2=Jaroslav|last2=Nešetřil|author2-link=Jaroslav Nešetřil|title=On the complexity of H-coloring|year=1990|journal=[[Journal of Combinatorial Theory]] | series=Series B|volume=48|issue=1|pages=92–110|doi=10.1016/0095-8956(90)90132-J|doi-access=free}}</ref>

This is also known as the ''dichotomy theorem'' for (undirected) graph homomorphisms, since it divides ''H''-coloring problems into NP-complete or P problems, with no [[NP-intermediate|intermediate]] cases.
For directed graphs, the situation is more complicated and in fact equivalent to the much more general question of characterizing the [[Complexity of constraint satisfaction|complexity of constraint satisfaction problems]].{{sfn|Hell|Nešetřil|2004|loc=§5.3}}
It turns out that ''H''-coloring problems for directed graphs are just as general and as diverse as CSPs with any other kinds of constraints.{{sfn|Hell|Nešetřil|2004|loc=Theorem 5.14}}<ref name="FederVardi">{{citation|first1=Tomás|last1=Feder|first2=Moshe Y.|last2=Vardi|author2-link=Moshe Y. Vardi|title=The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory|year=1998|journal=[[SIAM Journal on Computing]]|volume=28|issue=1|pages=57–104|doi=10.1137/S0097539794266766|url=http://theory.stanford.edu/~tomas/constraint.ps}}</ref> Formally, a (finite) ''constraint language'' (or ''template'') ''Γ'' is a finite domain and a finite set of relations over this domain. CSP(''Γ'') is the constraint satisfaction problem where instances are only allowed to use constraints in ''Γ''. 
: '''Theorem''' (Feder, [[Moshe Y. Vardi|Vardi]] 1998): For every constraint language ''Γ'', the problem CSP(''Γ'') is equivalent under [[polynomial-time reduction]]s to some ''H''-coloring problem, for some directed graph ''H''.<ref name="FederVardi"/>

Intuitively, this means that every algorithmic technique or complexity result that applies to ''H''-coloring problems for directed graphs ''H'' applies just as well to general CSPs. In particular, one can ask whether the Hell–Nešetřil theorem can be extended to directed graphs. By the above theorem, this is equivalent to the Feder–Vardi conjecture (aka CSP conjecture, dichotomy conjecture) on CSP dichotomy, which states that for every constraint language ''Γ'', CSP(''Γ'') is NP-complete or in P.{{sfn|Bodirsky|2007|loc=§1.3}} This conjecture was proved in 2017 independently by Dmitry Zhuk and Andrei Bulatov, leading to the following corollary:
: '''Corollary''' (Bulatov 2017; Zhuk 2017): The ''H''-coloring problem on directed graphs, for a fixed ''H'', is either in P or NP-complete.

===Homomorphisms from a fixed family of graphs===
The homomorphism problem with a single fixed graph ''G'' on left side of input instances can be solved by [[Brute-force search|brute-force]] in time |''V''(''H'')|<sup>O(|''V''(''G'')|)</sup>, so polynomial in the size of the input graph ''H''.<ref>{{citation
 | last1 = Cygan | first1 = Marek
 | last2 = Fomin | first2 = Fedor V. | author2-link = Fedor Fomin
 | last3 = Golovnev | first3 = Alexander
 | last4 = Kulikov | first4 = Alexander S.
 | last5 = Mihajlin | first5 = Ivan
 | last6 = Pachocki | first6 = Jakub
 | last7 = Socala | first7 = Arkadiusz
 | editor-last = Krauthgamer | editor-first = Robert
 | arxiv = 1507.03738
 | contribution = Tight bounds for graph homomorphism and subgraph isomorphism
 | doi = 10.1137/1.9781611974331.ch112
 | isbn = 978-1-611974-33-1
 | pages = 1643–1649
 | publisher = [[Society for Industrial and Applied Mathematics]]
 | title = Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10–12, 2016
 | year = 2016}}</ref> In other words, the problem is trivially in P for graphs ''G'' of bounded size. The interesting question is then what other properties of ''G'', beside size, make polynomial algorithms possible.

The crucial property turns out to be [[treewidth]], a measure of how tree-like the graph is. For a graph ''G'' of treewidth at most ''k'' and a graph ''H'', the homomorphism problem can be solved in time |''V''(''H'')|<sup>O(''k'')</sup> with a standard [[dynamic programming]] approach. In fact, it is enough to assume that the core of ''G'' has treewidth at most ''k''. This holds even if the core is not known.<ref>{{citation
 | last1 = Dalmau | first1 = Víctor
 | last2 = Kolaitis | first2 = Phokion G.
 | last3 = Vardi | first3 = Moshe Y. | author3-link = Moshe Vardi
 | editor-last = Van Hentenryck | editor-first = Pascal
 | contribution = Constraint satisfaction, bounded treewidth, and finite-variable logics
 | doi = 10.1007/3-540-46135-3_21
 | pages = 310–326
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Principles and Practice of Constraint Programming – CP 2002, 8th International Conference, CP 2002, Ithaca, NY, USA, September 9–13, 2002, Proceedings
 | volume = 2470
 | year = 2002| isbn = 978-3-540-44120-5
 }}</ref><ref name="Grohe">{{citation|first=Martin|last=Grohe|authorlink=Martin Grohe|title=The complexity of homomorphism and constraint satisfaction problems seen from the other side|volume=54|issue=1|pages=1–es|year=2007|journal=[[Journal of the ACM]]|doi=10.1145/1206035.1206036|s2cid=11797906}}</ref>

The exponent in the |''V''(''H'')|<sup>O(''k'')</sup>-time algorithm cannot be lowered significantly: no algorithm with running time |''V''(''H'')|<sup>o(tw(''G'') /log tw(''G''))</sup> exists, assuming the [[exponential time hypothesis]] (ETH), even if the inputs are restricted to any class of graphs of unbounded treewidth.<ref name="marx">{{citation|first=Dániel|last=Marx|title=Can You Beat Treewidth?|journal=[[Theory of Computing (journal)|Theory of Computing]]|year=2010|volume=6|pages=85–112|doi=10.4086/toc.2010.v006a005|doi-access=free}}</ref>
The ETH is an unproven assumption similar to [[P versus NP problem|P ≠ NP]], but stronger.
Under the same assumption, there are also essentially no other properties that can be used to get polynomial time algorithms. This is formalized as follows:
: '''Theorem''' ([[Martin Grohe|Grohe]]): For a [[Recursive set|computable]] class of graphs <math>\mathcal{G}</math>, the homomorphism problem for instances <math>(G,H)</math> with <math>G \in \mathcal{G}</math> is in P if and only if graphs in <math>\mathcal{G}</math> have cores of bounded treewidth (assuming ETH).<ref name="Grohe"/>

One can ask whether the problem is at least solvable in a time arbitrarily highly dependent on ''G'', but with a fixed polynomial dependency on the size of ''H''.
The answer is again positive if we limit ''G'' to a class of graphs with cores of bounded treewidth, and negative for every other class.<ref name="Grohe"/>
In the language of [[parameterized complexity]], this formally states that the homomorphism problem in <math>\mathcal{G}</math> parameterized by the size (number of edges) of ''G'' exhibits a dichotomy. It is [[fixed-parameter tractable]] if graphs in <math>\mathcal{G}</math> have cores of bounded treewidth, and [[Parameterized complexity#W.5B1.5D|W[1]]]-complete otherwise.

The same statements hold more generally for constraint satisfaction problems (or for relational structures, in other words). The only assumption needed is that constraints can involve only a bounded number of variables (all relations are of some bounded arity, 2 in the case of graphs). The relevant parameter is then the treewidth of the [[primal constraint graph]].<ref name="marx"/>

== See also ==
* [[Glossary of graph theory terms]]
* [[Homomorphism]], for the same notion on different algebraic structures
* [[Graph rewriting]]
* [[Median graph]]s, definable as the retracts of [[hypercube graph|hypercube]]s
* [[Sidorenko's conjecture]]

==Notes==
{{reflist}}

== References ==
=== General books and expositions ===
* {{citation|first=Peter|last=Cameron|author-link=Peter Cameron (mathematician)|title=Graph Homomorphisms, Combinatorics Study Group Notes|year=2006|url=http://www.maths.qmul.ac.uk/~pjc/csgnotes/hom1.pdf}}
* {{citation |last1=Hell |first1=Pavol|author-link=Pavol Hell |author2-link=Jaroslav Nešetřil|last2=Nešetřil | first2=Jaroslav |publisher=Oxford University Press |title=Graphs and Homomorphisms|series=Oxford Lecture Series in Mathematics and Its Applications|volume=28|year=2004 |isbn=0-19-852817-5|url=https://www2.cs.sfu.ca/~pavol/hombook.html}}
* {{citation|first1=Geňa|last1=Hahn|first2=Claude|last2=Tardif|contribution=Graph homomorphisms: structure and symmetry|title=Graph Symmetry: Algebraic Methods and Applications|publisher=Springer|year=1997|pages=107–166|doi=10.1007/978-94-015-8937-6_4|isbn=978-90-481-4885-1 |url=http://www.mast.queensu.ca/~ctardif/articles/ghss.pdf|access-date=2017-04-09|archive-date=2021-07-11|archive-url=https://web.archive.org/web/20210711070549/https://mast.queensu.ca/~ctardif/articles/ghss.pdf|url-status=dead}}
* {{citation|first1=Chris|last1=Godsil|author-link=Chris Godsil |first2=Gordon|last2=Royle|author2-link=Gordon Royle|title=Algebraic Graph Theory|doi=10.1007/978-1-4613-0163-9|isbn=978-1-4613-0163-9|year=2001|publisher=Springer–Verlag New York|series=Graduate Texts in Mathematics|volume=207|chapter=6. Homomorphisms|s2cid=9661174|url=https://www.math.uwaterloo.ca/~cgodsil/agt2/index.html}}
* {{cite book | last=Lovász | first=László | author-link=László Lovász | title=Large Networks and Graph Limits | publisher=American Mathematical Soc. | publication-place=Providence, Rhode Island | date=2012 | isbn=978-0-8218-9085-1 | url=https://lovasz.web.elte.hu/bookxx/hombook-almost.final.pdf}}

=== In constraint satisfaction and universal algebra ===
* {{citation|first1=Manuel|last1=Bodirsky|title=Graph Homomorphisms and Universal Algebra, Course Notes |url=https://wwwpub.zih.tu-dresden.de/~bodirsky/Graph-Homomorphisms.pdf |year=2007}}
* {{citation|first1=Pavol|last1=Hell|author1-link=Pavol Hell|first2=Jaroslav|last2=Nešetřil|author2-link=Jaroslav Nešetřil|title=Colouring, constraint satisfaction, and complexity|year=2008|journal=Computer Science Review|volume=2|issue=3|pages=143–163|doi=10.1016/j.cosrev.2008.10.003|url=http://www.cs.sfu.ca/~pavol/cspCCC.pdf|access-date=2017-04-09|archive-date=2017-07-06|archive-url=https://web.archive.org/web/20170706115247/http://www.cs.sfu.ca/~pavol/cspCCC.pdf|url-status=dead}}

=== In lattice theory and category theory ===
* {{citation|first1=Ronald|last1=Brown|first2=Ifor|last2=Morris|first3=John|last3=Shrimpton|first4=Christopher D.|last4=Wensley| title=Graphs of morphisms of graphs|journal=[[Electronic Journal of Combinatorics]]|year=2008|volume=15|issue=1|page=A1|doi=10.37236/919|url=https://www.combinatorics.org/ojs/index.php/eljc/article/view/v15i1a1/pdf|doi-access=free}}
* {{citation|first=Charles T.|last=Gray|title=The Digraph Lattice|year=2014|url=http://vrs.amsi.org.au/wp-content/uploads/sites/6/2014/09/CORRECTED-digraph-lattice-Gray-updated.pdf}} ([[Australian Mathematical Sciences Institute|AMSI]] [http://vrs.amsi.org.au/projects/ Vacation Research Scholarships] {{Webarchive|url=https://web.archive.org/web/20180814235547/http://vrs.amsi.org.au/projects/ |date=2018-08-14 }}, student research report supervised by Brian Davey and Jane Pitkethly, [[La Trobe University]]).

[[Category:Graph theory]]
[[Category:Morphisms]]
[[Category:NP-complete problems]]