Article ID Journal Published Year Pages File Type
4657471 Journal of Combinatorial Theory, Series B 2006 7 Pages PDF
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