Abstract

A homomorphism from a graph $G$ to a graph $H$ is a mapping from the vertex set of $G$ to the vertex set of $H$ that preserve the adjacency. In the (di)graph homomorphism problem we are asked whether an input (di)graph $G$ admits a homomorphism to target (di)graph $H$ (often a fixed graph). There are several generalizations of graph homomorphism problem such as; list homomorphism problem, minimum cost homomorphism problems and approximation of minimum cost homomorphism problem. In the complexity classification of this type of problems the presence of certain combinatorial property in the target (di)graph makes the problem tractable. I will discuss several recent results of this type.
Based on joint works with Pavol Hell.



Information: