Fulek, Radoslav and Pach, János (2019) Thrackles: An improved upper bound. DISCRETE APPLIED MATHEMATICS, 259. pp. 226-231. ISSN 0166-218X
|
Text
170808037.pdf Available under License Creative Commons Attribution. Download (335kB) | Preview |
Official URL: http://doi.org/10.1016/j.dam.2018.12.025
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 |
