On the local density problem for graphs of given odd-girth

Abstract

Erdős conjectured that every $n$-vertex triangle-free graph contains a subset of $\lfloor n/2\rfloor$ vertices that spans at most $n^2/50$ edges. Extending a recent result of Norin and Yepremyan, we confirm this conjecture for graphs homomorphic to so-called Andrásfai graphs. As a consequence, Erdős' conjecture holds for every triangle-free graph $G$ with minimum degree $\delta (G)>10n/29$ and if $\chi (G)\le 3$ the degree condition can be relaxed to $\delta (G)>n/3$. In fact, we obtain a more general result for graphs of higher odd-girth.

References in corpus (1)

• The homomorphism threshold of $\{C_3,C_5\}$-free graphs

Cited by in corpus (4)

• The Spectrum of Triangle-free Graphs
• Andrásfai and Vega graphs in Ramsey-Turán theory
• Sparse halves in $K_4$-free graphs
• K_4-free graphs have sparse halves