On Conway's thrackle conjecture

L. Lovász; J. Pach; M. Szegedy

doi:10.1007/PL00009322

On Conway's thrackle conjecture

L. Lovász, J. Pach, M. Szegedy

Research output: Contribution to journal › Article › peer-review

56 Scopus citations

Abstract

A thrackle is a graph drawn in the plane so that its edges are represented by Jordan arcs and any two distinct arcs either meet at exactly one common vertex or cross at exactly one point interior to both arcs. About 40 years ago, J. H. Conway conjectured that the number of edges of a thrackle cannot exceed the number of its vertices. We show that a thrackle has at most twice as many edges as vertices. Some related problems and generalizations are also considered.

Original language	English (US)
Pages (from-to)	369-376
Number of pages	8
Journal	Discrete and Computational Geometry
Volume	18
Issue number	4
DOIs	https://doi.org/10.1007/PL00009322
State	Published - Dec 1997
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1007/PL00009322

Cite this

@article{97e6755e5afa42dfbb2b5dbdc2564caa,

title = "On Conway's thrackle conjecture",

abstract = "A thrackle is a graph drawn in the plane so that its edges are represented by Jordan arcs and any two distinct arcs either meet at exactly one common vertex or cross at exactly one point interior to both arcs. About 40 years ago, J. H. Conway conjectured that the number of edges of a thrackle cannot exceed the number of its vertices. We show that a thrackle has at most twice as many edges as vertices. Some related problems and generalizations are also considered.",

author = "L. Lov{\'a}sz and J. Pach and M. Szegedy",

year = "1997",

month = dec,

doi = "10.1007/PL00009322",

language = "English (US)",

volume = "18",

pages = "369--376",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "4",

}

TY - JOUR

T1 - On Conway's thrackle conjecture

AU - Lovász, L.

AU - Pach, J.

AU - Szegedy, M.

PY - 1997/12

Y1 - 1997/12

N2 - A thrackle is a graph drawn in the plane so that its edges are represented by Jordan arcs and any two distinct arcs either meet at exactly one common vertex or cross at exactly one point interior to both arcs. About 40 years ago, J. H. Conway conjectured that the number of edges of a thrackle cannot exceed the number of its vertices. We show that a thrackle has at most twice as many edges as vertices. Some related problems and generalizations are also considered.

AB - A thrackle is a graph drawn in the plane so that its edges are represented by Jordan arcs and any two distinct arcs either meet at exactly one common vertex or cross at exactly one point interior to both arcs. About 40 years ago, J. H. Conway conjectured that the number of edges of a thrackle cannot exceed the number of its vertices. We show that a thrackle has at most twice as many edges as vertices. Some related problems and generalizations are also considered.

UR - http://www.scopus.com/inward/record.url?scp=0040645474&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0040645474&partnerID=8YFLogxK

U2 - 10.1007/PL00009322

DO - 10.1007/PL00009322

M3 - Article

AN - SCOPUS:0040645474

SN - 0179-5376

VL - 18

SP - 369

EP - 376

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 4

ER -

On Conway's thrackle conjecture

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this