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.