Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4657471 | Journal of Combinatorial Theory, Series B | 2006 | 7 Pages |
Abstract
One of Erdős' favourite conjectures was that any triangle-free graph G on n vertices should contain a set of n/2 vertices that spans at most n2/50 edges. We prove this when the number of edges in G is either at most n2/12 or at least n2/5.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics