کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4651924 | 1632582 | 2015 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Triangle-Free Subgraphs of Random Graphs
ترجمه فارسی عنوان
زیرگرافهای سه گانه رایگان نمودارهای تصادفی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
The Andrásfai–Erdős–Sós Theorem [Andrásfai, B., P. Erdős and V. T. Sós, On the connection between chromatic number, maximal clique and minimal degree of a graph, Discrete Math. 8 (1974), pp. 205–218] states that all triangle-free graphs on n vertices with minimum degree strictly greater than 2n/5 are bipartite. Thomassen [Thomassen, C., On the chromatic number of triangle-free graphs of large minimum degree, Combinatorica 22 (2002), pp. 591–596] proved that when the minimum degree condition is relaxed to , the result is still guaranteed to be rε-partite, where rε does not depend on n. We prove best possible random graph analogues of these theorems.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 49, November 2015, Pages 393-397
Journal: Electronic Notes in Discrete Mathematics - Volume 49, November 2015, Pages 393-397