Conway's thrackle conjecture

From Wikipedia, the free encyclopedia

A thrackle is an embedding (in the plane) of a graph, such that each edge is a Jordan arc 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.[1]

A thrackle embedding of a 6-cycle graph.
A thrackle embedding of a 6-cycle graph.

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.

Equivalently, the thrackle conjecture may be stated as every thrackle is a pseudoforest. More specifically, if the thrackle conjecture is true, the thrackles may be exactly characterized by a result of Woodall: they are the pseudoforests in which there is no cycle of length four and at most one odd cycle.[1][2]

It has been proven 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; this is also attainable.

Lovász et al. proved that every bipartite thrackle is a planar graph, although not drawn in a planar way.[1] As a consequence, they show that every thrackleable graph with n vertices has at most 2n − 3 edges. Since then, this bound has been improved, and it is now known that every thrackle has at most 3(n − 1)/2 edges.[3]

If the conjecture is false, a minimal counterexample would have the form of two even cycles sharing a vertex.[2] Therefore, to prove the conjecture, it would suffice to prove that graphs of this type cannot be drawn as thrackles.

[edit] References

  1. ^ a b c Lovász, L.; Pach, J. & Szegedy, M. (1997), “On Conway's thrackle conjecture”, Discrete and Computational Geometry 18: 369–376, MR1476318, DOI 10.1007/PL00009322 . A preliminary version of these results was reviewed in O'Rourke, J. (1995), “Computational geometry column 26”, ACM SIGACT News 26 (2): 15–17, DOI 10.1145/202840.202842 .
  2. ^ a b Woodall, D. R. (1969), “Thrackles and deadlock”, in Welsh, D. J. A., Combinatorial Mathematics and Its Applications, Academic Press, pp. 335–348, MR0277421 .
  3. ^ Cairns, G. & Nikolayevsky, Y. (2000), “Bounds for generalized thrackles”, Discrete and Computational Geometry 23 (2): 191–206, MR1739605, DOI 10.1007/PL00009495 .

[edit] External links