کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903541 | 1632743 | 2018 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Stability results for graphs with a critical edge
ترجمه فارسی عنوان
نتایج ثبات برای نمودار با یک لبه بحرانی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
The classical stability theorem of ErdÅs and Simonovits states that, for any fixed graph with chromatic number k+1â¥3, the following holds: every n-vertex graph that is H-free and has within o(n2) of the maximal possible number of edges can be made into the k-partite Turán graph by adding and deleting o(n2) edges. In this paper, we prove sharper quantitative results for graphs H with a critical edge, both for the ErdÅs-Simonovits Theorem (distance to the Turán graph) and for the closely related question of how close an H-free graph is to being k-partite. In many cases, these results are optimal to within a constant factor.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 74, December 2018, Pages 27-38
Journal: European Journal of Combinatorics - Volume 74, December 2018, Pages 27-38
نویسندگان
Alexander Roberts, Alex Scott,