کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4657471 1343739 2006 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Sparse halves in triangle-free graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Sparse halves in triangle-free graphs
چکیده انگلیسی

One of Erdős' favourite conjectures was that any triangle-free graph G on n vertices should contain a set of n/2 vertices that spans at most n2/50 edges. We prove this when the number of edges in G is either at most n2/12 or at least n2/5.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 96, Issue 4, July 2006, Pages 614-620