Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4652980 | Electronic Notes in Discrete Mathematics | 2007 | 7 Pages |
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