Thrackles: An improved upper bound

R. Fulek, J. Pach, Discrete Applied Mathematics (2019).

Download
No fulltext has been uploaded. References only!
Journal Article | Epub ahead of print | English
Author
Department
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 [Formula presented](n−1), and that this bound is best possible for infinitely many values of n.
Publishing Year
Date Published
2019-01-11
Journal Title
Discrete Applied Mathematics
ISSN
IST-REx-ID

Cite this

Fulek R, Pach J. Thrackles: An improved upper bound. Discrete Applied Mathematics. 2019. doi:10.1016/j.dam.2018.12.025
Fulek, R., & Pach, J. (2019). Thrackles: An improved upper bound. Discrete Applied Mathematics. https://doi.org/10.1016/j.dam.2018.12.025
Fulek, Radoslav, and János Pach. “Thrackles: An Improved Upper Bound.” Discrete Applied Mathematics, 2019. https://doi.org/10.1016/j.dam.2018.12.025.
R. Fulek and J. Pach, “Thrackles: An improved upper bound,” Discrete Applied Mathematics, 2019.
Fulek R, Pach J. 2019. Thrackles: An improved upper bound. Discrete Applied Mathematics.
Fulek, Radoslav, and János Pach. “Thrackles: An Improved Upper Bound.” Discrete Applied Mathematics, Elsevier, 2019, doi:10.1016/j.dam.2018.12.025.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar