Combinatorics Seminar 2015

Speaker: Yangjing Long (龍暘靖), Shanghai Jiao Tong University

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.