کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4657396 1343735 2006 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the minimal degree implying equality of the largest triangle-free and bipartite subgraphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
On the minimal degree implying equality of the largest triangle-free and bipartite subgraphs
چکیده انگلیسی

Erdős posed the problem of finding conditions on a graph G that imply t(G)=b(G), where t(G) is the largest number of edges in a triangle-free subgraph and b(G) is the largest number of edges in a bipartite subgraph. Let δc be the least number so that any graph G on n vertices with minimum degree δcn has t(G)=b(G). Extending results of Bondy, Shen, Thomassé and Thomassen we show that 0.75⩽δc<0.791.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 96, Issue 6, November 2006, Pages 919-932