2013/11/22 by Sergey Norin, Liana Yepremyan, Norin, Sergey +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1311.5818
23 pages
openalex publication_date 2013/11/22 · arxiv created 2015/02/10 · arxiv updated 2015/02/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Erdős conjectured that every triangle-free graph G on n vertices contains a set of \lfloor n/2 \rfloor vertices that spans at most n2 /50 edges. Krivelevich proved the conjecture for graphs with minimum degree at least (2)/(5)n. 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) - ε)n for some absolute ε >0. Moreover, we show that the conjecture is true for graphs which are close to the Petersen graph in edit distance.