On the geometric Ramsey numbers of trees

Pu Gao

paper

On the geometric Ramsey numbers of trees

arXiv:1308.5188

Abstract

In this paper, we obtain upper bounds for the geometric Ramsey numbers of trees. We prove that $R_{c} (T_{n}, H_{m}) = (n - 1) (m - 1) + 1$ if $T_{n}$ is a caterpillar and $H_{m}$ is a Hamiltonian outerplanar graph on $m$ vertices. Moreover, if $T_{n}$ has at most two non-leaf vertices, then $R_{g} (T_{n}, H_{m}) = (n - 1) (m - 1) + 1$ . We also prove that $R_{c} (T_{n}, H_{m}) = O (n^{2} m)$ and $R_{g} (T_{n}, H_{m}) = O (n^{3} m^{2})$ if $T_{n}$ is an arbitrary tree on $n$ vertices and $H_{m}$ is an outerplanar triangulation with pathwidth 2. %Further, we prove a uniform polynomial upper bound for the geometric Ramsey numbers of caterpillars and we also give an upper bound for $R_{g} (T_{n})$ where $T_{n}$ is an arbitrary tree.