کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4646829 1342314 2016 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the geometric Ramsey numbers of trees
ترجمه فارسی عنوان
درباره اعداد هندسی رمزی درختان
کلمات کلیدی
عدد رمزی هندسی؛ درخت؛ نمودار Outerplanar؛ کاترپیلار
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

In this paper, we estimate the geometric Ramsey numbers of trees. Given a tree TnTn on nn vertices and an outerplanar graph HmHm on mm vertices, we estimate the minimum number M=M(Tn,Hm)M=M(Tn,Hm) such that, for any set of MM points in the plane such that no three of them are collinear, and for any 2-colouring of the segments determined by the MM points, either the first colour class contains a non-crossing copy of TnTn, or the second colour class contains a non-crossing copy of HmHm. We prove that M(Tn,Hm)=(n−1)(m−1)+1M(Tn,Hm)=(n−1)(m−1)+1 if (i) the points are in convex position, TnTn is a caterpillar and HmHm is Hamiltonian, or if (ii) the points are in general position, TnTn has at most two non-leaf vertices, and HmHm is Hamiltonian. We also prove several polynomial bounds for M(Tn,Hm)M(Tn,Hm) for other classes of TnTn and HmHm.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 339, Issue 1, 6 January 2016, Pages 375–381
نویسندگان
,