Author/Authors :
Ne?et?il، نويسنده , , Jaroslav and Nigussie، نويسنده , , Yared، نويسنده ,
Abstract :
Let K be a class of finite graphs and F = { F 1 , F 2 , … , F m } be a set of finite graphs. Then, K is said to have finite-duality if there exists a graph U in K such that for any graph G in K , G is homomorphic to U if and only if F i is not homomorphic to G, for all i = 1 , 2 , … , m . Nešetřil asked in [J. Nešetřil, Homonolo Combinatorics Workshop, Nova Louka, Czech Rep., (2003)] if non-trivial examples can be found.
s note, we answer this positively by showing classes containing arbitrary long anti-chains and yet having the finite-duality property.