REAL

Thrackles: An improved upper bound

Fulek, R. and Pach, János (2018) Thrackles: An improved upper bound. LECTURE NOTES IN COMPUTER SCIENCE, 10692. pp. 160-166. ISSN 0302-9743

[img]
Preview
Text
1708.08037v1.pdf

Download (335kB) | Preview

Abstract

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 International Publishing AG 2018.

Item Type: Article
Uncontrolled Keywords: Drawing (graphics); Upper Bound; VISUALIZATION
Subjects: Q Science / természettudomány > QA Mathematics / matematika
SWORD Depositor: MTMT SWORD
Depositing User: MTMT SWORD
Date Deposited: 16 Aug 2018 13:37
Last Modified: 16 Aug 2018 13:37
URI: http://real.mtak.hu/id/eprint/82745

Actions (login required)

Edit Item Edit Item