Finite Duality for Some Minor Closed Classes

Document Type

Article

Publication Date

8-15-2007

Description

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.

Share

COinS