Abstract
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 εn 2, 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.
Original language | English (US) |
---|---|
Pages (from-to) | 23-30 |
Number of pages | 8 |
Journal | Annals of Discrete Mathematics |
Volume | 43 |
Issue number | C |
DOIs | |
State | Published - 1989 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics