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.
Citation Information
Nešetřil, Jaroslav; and Nigussie, Yared. 2007. Finite Duality for Some Minor Closed Classes. Electronic Notes in Discrete Mathematics. Vol.29(SPEC. ISS.). 579-585. https://doi.org/10.1016/j.endm.2007.07.092 ISSN: 1571-0653