zbMATH — the first resource for mathematics

Bounds for generalized thrackles. (English) Zbl 0959.05030
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.

05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX Cite
Full Text: DOI