REAL

Thrackles: An improved upper bound

Fulek, Radoslav and Pach, János (2019) Thrackles: An improved upper bound. DISCRETE APPLIED MATHEMATICS, 259. pp. 226-231. ISSN 0166-218X

[img]
Preview
Text
170808037.pdf
Available under License Creative Commons Attribution.

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.

Item Type: Article
Uncontrolled Keywords: projective plane; graph embedding; Thrackle; Parity embedding; 2-dimensional surface;
Subjects: Q Science / természettudomány > QA Mathematics / matematika
SWORD Depositor: MTMT SWORD
Depositing User: MTMT SWORD
Date Deposited: 19 Oct 2019 04:35
Last Modified: 17 Apr 2023 14:52
URI: http://real.mtak.hu/id/eprint/102416

Actions (login required)

Edit Item Edit Item