On the Geometric Ramsey Number of Outerplanar Graphs

0479815 - ÚI 2018 US eng J - Článek v odborném periodiku
Cibulka, J. - Gao, P. - Krčál, Marek - Valla, T. - Valtr, P.
On the Geometric Ramsey Number of Outerplanar Graphs.
Discrete & Computational Geometry. Roč. 53, č. 1 (2015), s. 64-79. ISSN 0179-5376. E-ISSN 1432-0444
Klíčová slova: minors * Geometric Ramsey theory * Outerplanar graph * Ordered Ramsey theory * Pathwidth
Impakt faktor: 0.816, rok: 2015

We prove polynomial upper bounds of geometric Ramsey numbers of pathwidth- outerplanar triangulations in both convex and general cases. We also prove that the geometric Ramsey numbers of the ladder graph on vertices are bounded by and , in the convex and general case, respectively. We then apply similar methods to prove an upper bound on the Ramsey number of a path with ordered vertices.
Trvalý link: http://hdl.handle.net/11104/0275742