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