Article ID Journal Published Year Pages File Type
4652157 Electronic Notes in Discrete Mathematics 2013 8 Pages PDF
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