On 11.12.2008 at 12:20 in S8, there is the following noon lecture:
The complexity of the list homomorphism problem for graphs
Concordia University, Montreal
(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.
Webmaster: kamweb.mff.cuni.cz Modified: 25. 02. 2019