Bounds for generalized thrackles (Q1971504): Difference between revisions

A thrackle (or a generalized thrackle) is a drawing of a graph in which each pair of edges meet precisely once (or an odd number of times, respectively). For a graph with \(n\) vertices and \(m\) edges it is shown that \(m\leq 3(n-1)/2\) for thrackles in a plane, while \(m\leq 2n-2\) for generalized thrackles in a plane; this improves known results by Lovász, Pach and Szegedy. The paper also examines thrackles on closed surfaces, with the following main result: A bipartite graph can be drawn as a generalized thrackle on a closed connected orientable surface if and only if the graph can be embedded in that surface.