More about sparse halves in triangle-free graphs

Abstract

One of Erdos's conjectures states that every triangle-free graph on $n$ vertices has an induced subgraph on $n/2$ vertices with at most $n^2/50$ edges. We report several partial results towards this conjecture. In particular, we establish the new bound $\frac{27}{1024}{n}^2$ on the number of edges in general case. We completely prove the conjecture for graphs of girth $\ge 5$, for graphs with independence number $\ge 2n/5$ and for strongly regular graphs. Each of these three classes includes both known (conjectured) extremal configurations, the 5-cycle and the Petersen graph.

25 pages. One more result (Theorem 3.5) has been added

Cited by in corpus (2)

• The Spectrum of Triangle-free Graphs
• 10 Problems for Partitions of Triangle-free Graphs