Earlier Version

Thrackles: An Improved Upper Bound

R. Fulek, J. Pach, in:, Springer, 2018, pp. 160–166.


Conference Paper | Published | English
Author
Department
Series Title
LNCS
Abstract
A thrackle is a graph drawn in the plane so that every pair of its edges meet exactly once: either at a common end vertex or in a proper crossing. We prove that any thrackle of n vertices has at most 1.3984n edges. Quasi-thrackles are defined similarly, except that every pair of edges that do not share a vertex are allowed to cross an odd number of times. It is also shown that the maximum number of edges of a quasi-thrackle on n vertices is 3/2(n-1), and that this bound is best possible for infinitely many values of n.
Publishing Year
Date Published
2018-01-21
Volume
10692
Page
160 - 166
IST-REx-ID

Cite this

Fulek R, Pach J. Thrackles: An Improved Upper Bound. In: Vol 10692. Springer; 2018:160-166. doi:10.1007/978-3-319-73915-1_14
Fulek, R., & Pach, J. (2018). Thrackles: An Improved Upper Bound (Vol. 10692, pp. 160–166). Springer. https://doi.org/10.1007/978-3-319-73915-1_14
Fulek, Radoslav, and János Pach. “Thrackles: An Improved Upper Bound,” 10692:160–66. Springer, 2018. https://doi.org/10.1007/978-3-319-73915-1_14.
R. Fulek and J. Pach, “Thrackles: An Improved Upper Bound,” 2018, vol. 10692, pp. 160–166.
Fulek R, Pach J. 2018. Thrackles: An Improved Upper Bound. , LNCS, vol. 10692. 160–166.
Fulek, Radoslav, and János Pach. Thrackles: An Improved Upper Bound. Vol. 10692, Springer, 2018, pp. 160–66, doi:10.1007/978-3-319-73915-1_14.

Link(s) to Main File(s)
Access Level
OA Open Access
Material in IST:
Later Version

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1708.08037

Search this title in

Google Scholar