On the geometric ramsey number of outerplanar graphs
Cibulka J, Gao P, Krcál M, Valla T, Valtr P. 2014. On the geometric ramsey number of outerplanar graphs. Discrete & Computational Geometry. 53(1), 64–79.
Download (ext.)
Journal Article
| Published
| English
Scopus indexed
Author
Cibulka, Josef;
Gao, Pu;
Krcál, MarekISTA;
Valla, Tomáš;
Valtr, Pavel
Department
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.
Publishing Year
Date Published
2014-11-14
Journal Title
Discrete & Computational Geometry
Publisher
Springer
Acknowledgement
Marek Krčál was supported by the ERC Advanced Grant No. 267165.
Volume
53
Issue
1
Page
64 - 79
IST-REx-ID
Cite this
Cibulka J, Gao P, Krcál M, Valla T, Valtr P. On the geometric ramsey number of outerplanar graphs. Discrete & Computational Geometry. 2014;53(1):64-79. doi:10.1007/s00454-014-9646-x
Cibulka, J., Gao, P., Krcál, M., Valla, T., & Valtr, P. (2014). On the geometric ramsey number of outerplanar graphs. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/s00454-014-9646-x
Cibulka, Josef, Pu Gao, Marek Krcál, Tomáš Valla, and Pavel Valtr. “On the Geometric Ramsey Number of Outerplanar Graphs.” Discrete & Computational Geometry. Springer, 2014. https://doi.org/10.1007/s00454-014-9646-x.
J. Cibulka, P. Gao, M. Krcál, T. Valla, and P. Valtr, “On the geometric ramsey number of outerplanar graphs,” Discrete & Computational Geometry, vol. 53, no. 1. Springer, pp. 64–79, 2014.
Cibulka J, Gao P, Krcál M, Valla T, Valtr P. 2014. On the geometric ramsey number of outerplanar graphs. Discrete & Computational Geometry. 53(1), 64–79.
Cibulka, Josef, et al. “On the Geometric Ramsey Number of Outerplanar Graphs.” Discrete & Computational Geometry, vol. 53, no. 1, Springer, 2014, pp. 64–79, doi:10.1007/s00454-014-9646-x.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Google Scholar