A homomorphism between graphs G and H is a vertex map from G to H that
carries edges in G to edges in H. A (proper) k-colouring of a graph G
can be seen as a homomorphism form G to K_k. From this point of view,
a natural generalisation of graph colouring is obtained by replacing
K_k by some arbitrary (but fixed) graph H. This is the graph
homomorphism problem with a fixed target graph H, also called the
H-Colouring Problem. The optimisation version of this problem, the
Maximum H-Colourable Subgraph Problem (Max H-Col), is the problem
where one seeks a vertex map from G to H that maximises the number of
edges in G mapped edges in H. For the complete graph H = K_k, this
problem has been studied under the name Max k-cut. Max k-cut is
APX-complete but approximation algorithms exist that are conjectured
to have optimal performance.

I will present a simple approximation-preserving reduction between
Max H-Col problems that gives rise to a binary graph parameter with
interesting properties. The parameter is used to relate the
approximation ratios of different Max H-Col problems; in other words,
it allows the translation of approximability (and non-approximability)
results for one problem into (non)-approximability results for other
problems with a degradation in precision determined by the
parameter. Using the known approximation algorithms for Max k-cut in
combination with this reduction, I will show how to obtain general
asymptotic approximability results for Max H-Col.

Furthermore, I will discuss a close connection to work by Robert Smal
on cubical colourings of graphs. This connection provides a different
way of computing the parameter and raises a number of interesting
questions.

The talk is based on joint work with Robert Engstrm, Tommy Frnqvist,
and Peter Jonsson (Linkping University, Sweden).