Coast to Coast Seminar Series: Live From Burnaby, British Columbia "List Homomorphisms, Minimum Cost Homomorphisms, Interval and Circular Arc Graphs"

Abstract

In this introductory talk, I will discuss a connection between structural characterizations of some natural and traditional graph classes (such as those mentioned in the title), and certain complexity questions arising in the study of graph homomorphisms, or more generally constraint satisfaction problems. In particular, I will relate dichotomy classifications of such homomorphism problems to structural characterizations of the corresponding graph classes.