Towards Generalizing Thrackles to Arbitrary Graphs Jin-Woo Bryan Oh

In the 1950s, John Conway came up with the notion of thrackles, graphs with embeddings in which no edge crosses itself, but every pair of distinct edges intersects each other exactly once. He conjectured that |E(G) | ≤ |V (G) | for any thrackle G, a question unsolved to this day. In this paper, we discuss some of the known properties of thrackles and contribute a few new ones. Only a few sparse graphs can be thrackles, and so it is of interest to find an analogous notion that applies to denser graphs as well. In this paper we introduce a generalized version of thrackles called near-thrackles, and prove some of their properties. We also discuss a large number of conjectures about them which seem very obvious but nonetheless are hard to prove. In the final section, we introduce thrackleability, a number between 0 and 1 that turns out to be an accurate measure of how far away a graph is from being a thrackle.