On the local density problem for graphs of given odd-girth
classification
🧮 math.CO
keywords
graphsconjecturedegreedeltaeverygraphodd-girthresult
read the original abstract
Erd\H{o}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\'asfai graphs. As a consequence, Erd\H{o}s' conjecture holds for every triangle-free graph $G$ with minimum degree $\delta (G)>10n/29$ and if $\chi (G)\leq 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.