Let G be a graph on n vertices. We show that if the total number of isomorphism types of induced subgraphs of G is at most εn2, where ε<10-21, then either G or its complement contain an independent set on at least (1-4ε)n vertices. This settles a problem of Erdős and Hajnal.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics