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.
Identifer | oai:union.ndltd.org:ETSU/oai:dc.etsu.edu:etsu-works-19051 |
Date | 15 August 2007 |
Creators | Nešetřil, Jaroslav, Nigussie, Yared |
Publisher | Digital Commons @ East Tennessee State University |
Source Sets | East Tennessee State University |
Detected Language | English |
Type | text |
Source | ETSU Faculty Works |
Page generated in 0.0094 seconds