Known Bounds
Lovász et al. proved that every bipartite thrackle is a planar graph, although not drawn in a planar way. 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 two times. First, it was improved to 3(n − 1)/2, and the current best bound is roughly 1.428n. Moreover, the method used to prove this result yields for any ε>0 a finite algorithm that either improves the bound to (1 + ε)n or disproves the conjecture.
If the conjecture is false, a minimal counterexample would have the form of two even cycles sharing a vertex. Therefore, to prove the conjecture, it would suffice to prove that graphs of this type cannot be drawn as thrackles.
Read more about this topic: Conway's Thrackle Conjecture
Famous quotes containing the word bounds:
“At bounds of boundless void.”
—Samuel Beckett (1906–1989)
“Prohibition will work great injury to the cause of temperance. It is a species of intemperance within itself, for it goes beyond the bounds of reason in that it attempts to control a man’s appetite by legislation, and makes a crime out of things that are not crimes. A Prohibition law strikes a blow at the very principles upon which our government was founded.”
—Abraham Lincoln (1809–1865)