Article ID Journal Published Year Pages File Type
4652980 Electronic Notes in Discrete Mathematics 2007 7 Pages PDF
Abstract

Let K be a class of finite graphs and F={F1,F2,…,Fm} 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 Fi 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.In this note, we answer this positively by showing classes containing arbitrary long anti-chains and yet having the finite-duality property.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics