Thrackles: An improved upper bound
LNCS
Fulek, Radoslav
Pach, János
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.
Springer
2018
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
https://research-explorer.app.ist.ac.at/record/433
Fulek R, Pach J. Thrackles: An improved upper bound. In: Vol 10692. Springer; 2018:160-166. doi:<a href="https://doi.org/10.1007/978-3-319-73915-1_14">10.1007/978-3-319-73915-1_14</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-319-73915-1_14
info:eu-repo/semantics/altIdentifier/arxiv/1708.08037
info:eu-repo/semantics/openAccess