Article ID Journal Published Year Pages File Type
4646829 Discrete Mathematics 2016 7 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,