کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4652980 1632602 2007 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Finite duality for some minor closed classes
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Finite duality for some minor closed classes
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 29, 15 August 2007, Pages 579-585