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:
“Nature seems at each man’s birth to have marked out the bounds of his virtues and vices, and to have determined how good or how wicked that man shall be capable of being.”
—François, Duc De La Rochefoucauld (1613–1680)
“What comes over a man, is it soul or mind
That to no limits and bounds he can stay confined?
You would say his ambition was to extend the reach
Clear to the Arctic of every living kind.
Why is his nature forever so hard to teach
That though there is no fixed line between wrong and right,
There are roughly zones whose laws must be obeyed?”
—Robert Frost (1874–1963)