Pims/Mitacs Discrete Mathematics Seminar
Tuesday, 28 February 2001 from 3:30 - 4:30 in K9509

Pavol Hell
Talks on

Abstract: List homomorphisms generalize list colourings, and homomorphisms, and are in many ways more natural than unrestricted homomorphisms. I will survey known results on the complexity of list homomorphisms, and show the new final characterization of graphs for which the list homomorphism problem is polynomial time solvable. I will also describe a natural extension of list homomorphisms (symmetrized with respect to complementation), which includes many well known combinatorial problems related to graph perfection.