Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On the Bounds of Conway’s Thrackles

  • Published:
Discrete & Computational Geometry Aims and scope Submit manuscript

Abstract

A thrackle on a surface X is a graph of size e and order n drawn on X such that every two distinct edges of G meet exactly once either at their common endpoint, or at a proper crossing. An unsolved conjecture of Conway (1969) asserts that \(e\le n\) for every thrackle on a sphere. Until now, the best known bound is \(e\le 1.428n\). By using discharging rules we show that \(e\le 1.4n-1.4\).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  1. Archdeacon, D., Stor, K.: Superthrackles. Australas. J. Comb. 67(2), 145–158 (2017)

    MathSciNet  Google Scholar 

  2. Bondy, J.A., Murty, U.S.R.: Graph Theory. Graduate Texts in Mathematics, vol. 244. Springer, New York (2008)

    MATH  Google Scholar 

  3. Cairns, G., Nikolayevsky, Yu.: Bounds for generalized thrackles. Discrete Comput. Geom. 23(2), 191–206 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  4. Cairns, G., Nikolayevsky, Yu.: Generalized thrackle drawings of non-bipartite graphs. Discrete Comput. Geom. 41(1), 119–134 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  5. Cairns, G., Nikolayevsky, Yu.: Outerplanar thrackles. Graphs Combin. 28(1), 85–96 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  6. Fulek, R., Pach, J.: A computational approach to Conway’s thrackle conjecture. Comput. Geom. 44(6–7), 345–355 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  7. Lovász, L., Pach, J., Szegedy, M.: On Conway’s thrackle conjecture. Discrete Comput. Geom. 18(4), 369–376 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  8. Mohar, B., Thomassen, C.: Graphs on Surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore (2001)

    Google Scholar 

  9. Woodall, D.R.: Thrackles and Deadlock. In: Walsh, D.J.A. (ed.) Combinatorial Mathematics and Its Applications, pp. 335–347. Academic Press, London (1971)

    Google Scholar 

Download references

Acknowledgements

We would like to thank the referees for their great suggestions which helped us a lot in improving the presentation, especially for their suggestions on reducing the upper bound from 1.4n to \(1.4(n-1)\).

Author information

Authors and Affiliations

  1. Department of Mathematics, Simon Fraser University, Burnaby, BC, V5A 1S6, Canada

    Luis Goddyn

  2. School of Mathematics and Statistics, The University of Western Australia, Perth, WA, 6009, Australia

    Yian Xu

Authors
  1. Luis Goddyn
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yian Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yian Xu.

Additional information

Editor in Charge: János Pach

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Goddyn, L., Xu, Y. On the Bounds of Conway’s Thrackles. Discrete Comput Geom 58, 410–416 (2017). https://doi.org/10.1007/s00454-017-9877-8

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00454-017-9877-8

Keywords

Mathematics Subject Classification

Search

Navigation