Ramsey graphs contain many distinct induced subgraphs

N. Alon, A. Hajnal

Research output: Contribution to journalArticle

3 Scopus citations

Abstract

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
Volume7
Issue number1
DOIs
StatePublished - Mar 1 1991
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

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

  • Cite this