Thrackles: An improved upper bound
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 [Formula presented](n−1), and that this bound is best possible for infinitely many values of n.
Elsevier
2019
info:eu-repo/semantics/article
doc-type:article
text
http://purl.org/coar/resource_type/c_6501
https://research-explorer.app.ist.ac.at/record/5857
Fulek R, Pach J. Thrackles: An improved upper bound. <i>Discrete Applied Mathematics</i>. 2019;259(4):266-231. doi:<a href="https://doi.org/10.1016/j.dam.2018.12.025">10.1016/j.dam.2018.12.025</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1016/j.dam.2018.12.025
info:eu-repo/semantics/altIdentifier/issn/0166218X
info:eu-repo/semantics/altIdentifier/arxiv/1708.08037
info:eu-repo/grantAgreement/FWF//M02281
info:eu-repo/semantics/openAccess