Graphs with a small number of distinct induced subgraphs

Noga Alon, Béla Bollobás

Research output: Contribution to journalArticle

13 Scopus citations

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 ε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 Erdo&#x030B;s and Hajnal.

Original languageEnglish (US)
Pages (from-to)23-30
Number of pages8
JournalDiscrete Mathematics
Volume75
Issue number1-3
DOIs
StatePublished - May 1989
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Graphs with a small number of distinct induced subgraphs'. Together they form a unique fingerprint.

  • Cite this