pith. sign in

arxiv: 1406.2726 · v2 · pith:A7ECJMBRnew · submitted 2014-06-10 · 🧮 math.CO · cs.CG

Disjoint edges in topological graphs and the tangled-thrackle conjecture

classification 🧮 math.CO cs.CG
keywords edgeseverygraphpointcommonconjecturedisjointtangled-thrackle
0
0 comments X
read the original abstract

It is shown that for a constant $t\in \mathbb{N}$, every simple topological graph on $n$ vertices has $O(n)$ edges if it has no two sets of $t$ edges such that every edge in one set is disjoint from all edges of the other set (i.e., the complement of the intersection graph of the edges is $K_{t,t}$-free). As an application, we settle the \emph{tangled-thrackle} conjecture formulated by Pach, Radoi\v{c}i\'c, and T\'oth: Every $n$-vertex graph drawn in the plane such that every pair of edges have precisely one point in common, where this point is either a common endpoint, a crossing, or a point of tangency, has at most $O(n)$ edges.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.