# Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 11.12.2008 at 12:20 in S8, there is the following noon lecture:

# The complexity of the list homomorphism problem for graphs

## Benoit Larose

## Concordia University, Montreal

## Abstract

(joint work with L. Egri (McGill), A. Krokhin (Durham), P. Tesson (Laval))

We completely characterise the complexity of the list homomorphism problem for graphs in combinatorial and algebraic terms: for every graph $H$ the problem is either NP-complete, NL-complete, L-complete or has finite duality. The central result is an inductive definition of graphs whose problem is solvable in Logspace; a characterisation by forbidden subgraphs is given as well. In particular, the reflexive graphs whose list homomorphism is in Logspace are the trivially perfect graphs, or equivalently the $(P_4,C_4)$-free graphs. In the irreflexive case an analogous result is obtained: those with a list-hom problem in Logspace are the bipartite $(P_6,C_6)$-free graphs.

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz Modified: 19. 10. 2010