Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4646829 | Discrete Mathematics | 2016 | 7 Pages |
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.