Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903487 | Electronic Notes in Discrete Mathematics | 2017 | 6 Pages |
Abstract
ErdÅs conjectured that every n-vertex triangle-free graph contains a subset of ân/2â vertices that spans at most n2/50 edges. Extending a recent result of Norin and Yepremyan, we confirm this 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 δ(G)>10n/29 and if Ï(G)â¤3 the degree condition can be relaxed to δ(G)>n/3. In fact, we obtain a more general result for graphs of higher odd-girth.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Wiebke Bedenknecht, Guilherme Oliveira Mota, Christian Reiher, Mathias Schacht,