科研之友
微信
新浪微博
Facebook
分享链接
摘要
Erdos [3] conjectured that every triangle-free graph G on n vertices contains a set of [n/2.] vertices that spans at most n(2)/50 edges. Krivelevich proved the conjecture for graphs with minimum degree at least 2/5 n [9]. In [8] Keevash and Sudakov improved this result to graphs with average degree at least 2/5 n. We strengthen these results by showing that the conjecture holds for graphs with minimum degree at least 5/14 n and for graphs with average degree at least (2/5 - gamma) n for some absolute gamma > 0. Moreover, we show that the conjecture is true for graphs which are close to the Petersen graph in edit distance.
- 出版日期2015-11
- 单位McGill
