History


Please fill in your query. A complete syntax description you will find on the General Help page.
A computational approach to Conway’s thrackle conjecture. (English)
Comput. Geom. 44, No. 6-7, 345-355 (2011).
Summary: A drawing of a graph in the plane is called a thrackle if every pair of edges meets precisely once, either at a common vertex or at a proper crossing. Let $t(n)$ denote the maximum number of edges that a thrackle of $n$ vertices can have. According to a 40 years old conjecture of Conway, $t(n)=n$ for every $n \geqslant 3$. For any $ϵ> 0$, we give an algorithm terminating in $e^{O((1/ε^{2})\ln (1/ϵ))}$ steps to decide whether $t(n) \leqslant (1+ϵ)n$ for all $n\geqslant 3$. Using this approach, we improve the best known upper bound, $t(n) \leqslant \frac 32(n-1)$, due to Cairns and Nikolayevsky, to $\frac {167}{117}n < 1.428n$.
WorldCat.org
Valid XHTML 1.0 Transitional Valid CSS!