Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4652157 | Electronic Notes in Discrete Mathematics | 2013 | 8 Pages |
Abstract
In this paper we study a conjecture of Erdös that any triangle-free graph G on n vertices should contain a set of ⌊n/2⌋ vertices that spans at most n2/50 edges. Krivelevich proved the conjecture for graphs with minimum degree at least . Keevash and Sudakov improved this result to graphs with average degree at least . We strengthen these results further by showing that the conjecture holds for graphs with minimum degree at least and average degree at least for some absolute ϵ>0.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics