On the geometric Ramsey numbers of trees

Pu Gao

Research output: Contribution to journalArticleResearchpeer-review

Abstract

In this paper, we estimate the geometric Ramsey numbers of trees. Given a tree Tn on n vertices and an outerplanar graph Hm on m vertices, we estimate the minimum number M=M(Tn,Hm) such that, for any set of 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 points, either the first colour class contains a non-crossing copy of Tn, or the second colour class contains a non-crossing copy of Hm. We prove that M(Tn,Hm)=(n-1)(m-1)+1 if (i) the points are in convex position, Tn is a caterpillar and Hm is Hamiltonian, or if (ii) the points are in general position, Tn has at most two non-leaf vertices, and Hm is Hamiltonian. We also prove several polynomial bounds for M(Tn,Hm) for other classes of Tn and Hm.
Original languageEnglish
Article number10243
Pages (from-to)375-381
Number of pages7
JournalDiscrete Mathematics
Volume339
Issue number1
DOIs
Publication statusPublished - 2016

Keywords

  • Caterpillar
  • Geometric Ramsey number
  • Outerplanar graph
  • Pathwidth-2 outerplanar triangulation
  • Tree

Cite this