کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6424085 | 1632767 | 2016 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Disjoint edges in topological graphs and the tangled-thrackle conjecture
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
It is shown that for a constant tâN, every simple topological graph on n vertices has O(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 Kt,t-free). As an application, we settle the tangled-thrackle conjecture formulated by Pach, RadoiÄiÄ, and Tóth: 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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 51, January 2016, Pages 398-406
Journal: European Journal of Combinatorics - Volume 51, January 2016, Pages 398-406
نویسندگان
Andres J. Ruiz-Vargas, Andrew Suk, Csaba D. Tóth,