On the geometric ramsey number of outerplanar graphs Journal Article


Author(s): Cibulka, Josef; Gao, Pu; Krčál, Marek; Valla, Tomáš ; Valtr, Pavel
Article Title: On the geometric ramsey number of outerplanar graphs
Affiliation IST Austria
Abstract: We prove polynomial upper bounds of geometric Ramsey numbers of pathwidth-2 outerplanar triangulations in both convex and general cases. We also prove that the geometric Ramsey numbers of the ladder graph on 2n vertices are bounded by O(n3) and O(n10), in the convex and general case, respectively. We then apply similar methods to prove an (Formula presented.) upper bound on the Ramsey number of a path with n ordered vertices.
Keywords: Geometric Ramsey theory; Ordered Ramsey theory; Outerplanar graph; Pathwidth
Journal Title: Discrete & Computational Geometry
Volume: 53
Issue 1
ISSN: 0179-5376
Publisher: Springer  
Date Published: 2014-11-14
Start Page: 64
End Page: 79
URL:
DOI: 10.1007/s00454-014-9646-x
Notes: Research was supported by the project CE-ITI (GAČR P202/12/G061) of the Czech Science Foundation and by the Grant SVV-2014-260103. Josef Cibulka and Pavel Valtr were also supported by the project no. 52410 of the Grant Agency of Charles University. Pu Gao was supported by the Humboldt Foundation and is currently affiliated with University of Toronto. Marek Krčál was supported by the ERC Advanced Grant No. 267165. The authors would like to thank to Gyula Károlyi for introduction to the geometric Ramsey theory and to Jan Kynčl and Martin Balko for discussions about the Ramsey theory of ordered graphs. The authors are grateful to the anonymous referees for their valuable comments.
Open access: yes (repository)
IST Austria Authors
  1. Marek Krčál
    10 Krčál
Related IST Austria Work