2017/08/27 by Fulek, Radoslav, Pach, János · 3 citations
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1708.08037
A \em 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. \em Quasi-thrackles are defined similarly, except that every pair of edges that do not share a vertex are allowed to cross an \em odd number of times. It is also shown that the maximum number of edges of a quasi-thrackle on n vertices is 3\over 2(n-1), and that this bound is best possible for infinitely many values of n.