Abstract :

Polymorphisms are of interest in algebra and logic, and they are conjectured to be a universal tool for proving tractability of constraint satisfaction problems. I will illustrate their appeal and usefulness in graph theory, by giving a guided tour of some new and some well known graph classes defined by the existence of basic polymorphisms.

Biography :

Professor Hell obtained his PhD from Universite de Montreal in 1973, and has been a full professor at Simon Fraser University since 1983. His main research interests are algorithmic graph theory and the complexity of combinatorial problems. He has a monograph with Jarik Nesetril on Graphs and Homomorphisms (published by Oxford University Press) and has around 200 publications in journals and conferences. He is currently the managing editor of Journal of Graph Theory and also sits on the editorial boards of SIAM Journal on Discrete Math, Discrete Applied Mathematics, Order, and Contributions to Discrete Mathematics. He was a recent Chair of the Executive Board of the SIAM Activity Group on Discrete Mathematics (2006-2008), member of NSERC Grant Selection Committee 331 - Computing and Information Sciences B (2005-08), and currently sits on the BIRS Scientific Advisory Board (2008-2011), and the DIMATIA (Prague) International Scientific Advisory Board (since 2002).