10.1016/j.dam.2018.12.025
Fulek, Radoslav
Radoslav
Fulek0000-0001-8485-1774
Pach, János
János
Pach
Thrackles: An improved upper bound
Elsevier
2019
2019-01-20T22:59:17Z
2020-05-14T08:48:19Z
journal_article
/record/5857
/record/5857.json
0166218X
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 [Formula presented](n−1), and that this bound is best possible for infinitely many values of n.