Ramsey graphs contain many distinct induced subgraphs

N. Alon, A. Hajnal

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


It is shown that any graph on n vertices containing no clique and no independent set on t + 1 vertices has at least {Mathematical expression} distinct induced subgraphs.

Original languageEnglish (US)
Pages (from-to)1-6
Number of pages6
JournalGraphs and Combinatorics
Issue number1
StatePublished - Mar 1991
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Ramsey graphs contain many distinct induced subgraphs'. Together they form a unique fingerprint.

Cite this