کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4651924 1632582 2015 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Triangle-Free Subgraphs of Random Graphs
ترجمه فارسی عنوان
زیرگرافهای سه گانه رایگان نمودارهای تصادفی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

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