Titre : A new graph parameter and its relation to approximation properties of graph H-colouring Exposant : Johan Thapper, LIX 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 Samal 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 Engstroem, Tommy Faernqvist, and Peter Jonsson (Linkoeping University, Sweden).