Date: Sat, May 09, 2015
Time: 11:25 - 12:05
Venue: Middle Meeting Room
Title: Computational complexity of vertex-surjective homomorphisms
In this talk we will give an overview of the computational complexity aspect of graph surjective homomorphisms. We will show that that it is an NP-complete problem to decide the existence of a vertex-surjective homomorphism to an even cycle of length no less than 6, thus solving an open question in a recent paper by Bodirsky, Kara and Martin (On vertex surjective homomorphisms to cycles). This is joint work with Gary MacGillivray.