| Conways Thrackle Conjecture |
Article Index for Conways |
Website Links For Conways |
Information AboutConways Thrackle Conjecture |
| CATEGORIES ABOUT CONWAYS THRACKLE CONJECTURE | |
| conjectures | |
| topological graph theory | |
|
and every pair of edges meet once. Edges may either meet at a common endpoint, or, if they have no endpoints in common, at a point in their interiors. In the latter case, the crossing must be ''transverse''.L. Lovász, J. Pach, and M. Szegedy, On Conway's thrackle conjecture, Discrete Comput. Geom. 18 (1997), 369--376. John H. Conway has conjectured that in any thrackle the number of edges is at most equal to the number of vertices. Conway himself uses the terminology ''paths'' and ''spots'' (for ''edges'' and ''vertices'' respectively), so Conway's thrackle conjecture was originally stated in the form ''every thrackle has at least as many spots as paths.'' It has been proved that every cycle graph other than C4 has a thrackle embedding, which shows that the conjecture is sharp. That is, there are thrackles having the same number of spots as paths. At the other extreme, the worst case scenario is that the number of spots is twice the number of paths; which is also attainable. Lovász et al. (1997) proved that every Bipartite thrackle is a Planar Graph , although not drawn in a planar way. As a consequence, every such graph with ''n'' vertices has at most 2''n'' − 4 edges. Based on the same ideas, they show that every thrackle has at most 2''n'' − 4 edges. REFERENCES |
|
|