On the geometric Ramsey numbers of trees

详细信息    查看全文

• 作者：Pu Gao¹ ; ^{jane.gao@monash.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Geometric Ramsey number ; Tree ; Outerplanar graph ; Pathwidth-2 outerplanar triangulation ; Caterpillar
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 January 2016
• 年：2016
• 卷：339
• 期：1
• 页码：375-381
• 全文大小：382 K

文摘

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