Loading...
research article
Thrackles: An improved upper bound
April 30, 2019
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. (C) 2019 Published by Elsevier B.V.
Type
research article
Web of Science ID
WOS:000466061100020
Authors
Publication date
2019-04-30
Publisher
Published in
Volume
259
Start page
226
End page
231
Peer reviewed
REVIEWED
Written at
EPFL
EPFL units
Available on Infoscience
June 18, 2019
Use this identifier to reference this record