Polynomial bounds on geometric Ramsey numbers of ladder graphs

Abstrakt

We prove that the geometric Ramsey numbers of the ladder graph on 2n vertices are bounded by O(n^3) and O(n^10), in the convex and general case, respectively. We also prove polynomial upper bounds of geometric Ramsey numbers of pathwidth-2 outerplanar triangulations in both convex and general cases.

Klíčová slova

• geometric Ramsey numbers
• ladder graphs
• pathwidth-2 outerplanar triangulations