## “Bulletin Board”

School of Mathematics - December 18, 2013

### Mathematical Lecture

#### Graph Homomorphism Problem and its Generalizations Arash Rafiey Simon Fraser University Canada December 18, 2013

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:

 Date: Wednesday, December 18, 2013at 11:00-12:00 Place: Niavaran Bldg., Niavaran Square, Tehran, Iran