Résumé

It is shown that fora constant t is an element of N, every simple topological graph on n vertices has 0(n) edges if the graph 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,K-t-free). As an application, we settle the tangled-thrackle conjecture formulated by Pach, Radoicic, and Toth: 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. (C) 2015 Elsevier Ltd. All rights reserved.

Détails

Actions