Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Thrackles: An improved upper bound
 
research article

Thrackles: An improved upper bound

Fulek, Radoslav  
•
Pach, Janos  
April 30, 2019
Discrete Applied Mathematics

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. (C) 2019 Published by Elsevier B.V.

  • Details
  • Metrics
Type
research article
DOI
10.1016/j.dam.2018.12.025
Web of Science ID

WOS:000466061100020

Author(s)
Fulek, Radoslav  
Pach, Janos  
Date Issued

2019-04-30

Publisher

ELSEVIER SCIENCE BV

Published in
Discrete Applied Mathematics
Volume

259

Start page

226

End page

231

Subjects

Mathematics, Applied

•

Mathematics

•

thrackle

•

graph embedding

•

parity embedding

•

projective plane

•

2-dimensional surface

•

discharging method

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCG  
Available on Infoscience
June 18, 2019
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/157358
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés