# Noon lecture

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

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

# Nesetril dualities are decidable

## Yared Nigussie

## Abstract

Let K be a class of graphs. A pair (F, U) is a finite duality in K if F is a finite subset of K and U is a graph in K, such that for every G in K, G is homomorphic to U if and only if H is not homomorphic to G for all H in F. (F,U) is called a dual-pair. We study the case where K is the class of graphs embeddable on a fixed surface. A stronger form of duality, called Nesetril duality, is obtained from a graph U if for every surface S, in which U embeds there exists a finite set F(S) such that (F(S), U) is a dual pair in the class of graphs embeddable in S. We prove that the number of Nesetril dualities that can be found on each fixed surface is finite.

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