10.1007/978-3-319-73915-1_14
Fulek, Radoslav
Radoslav
Fulek0000-0001-8485-1774
Pach, János
János
Pach
Thrackles: An Improved Upper Bound
LNCS
Springer
2018
2018-12-11T11:46:27Z
2019-08-02T12:39:05Z
conference
https://research-explorer.app.ist.ac.at/record/433
https://research-explorer.app.ist.ac.at/record/433.json
1708.08037
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.