On the geometric Ramsey numbers of trees

DOI10.1016/J.DISC.2015.08.021zbMATH Open1322.05094arXiv1308.5188OpenAlexW1780397282MaRDI QIDQ501079FDOQ501079

Pu Gao

Publication date: 8 October 2015

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1308.5188

Recommendations

• On geometric graph Ramsey numbers
• Ramsey-type results for geometric graphs. I
• The Erdős-Sós conjecture for geometric graphs
• On the geometric Ramsey number of outerplanar graphs
• Ramsey numbers for trees

zbMATH Keywords

outerplanar graphcaterpillargeometric Ramsey numberpathwidth-2 outerplanar triangulation

Mathematics Subject Classification ID

Trees (05C05) Generalized Ramsey theory (05C55)

Cites Work

• Ramsey-type results for geometric graphs. II
• Ramsey-type results for geometric graphs. I
• A decomposition theorem for partially ordered sets
• Title not available (Why is that?)
• Crossing families
• Title not available (Why is that?)
• On geometric graph Ramsey numbers
• On the geometric Ramsey number of outerplanar graphs
• Ramsey-Type Problems for Geometric Graphs
• Generalized and geometric Ramsey numbers for cycles.

This page was built for publication: On the geometric Ramsey numbers of trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q501079)