Ramsey graphs contain many distinct induced subgraphs

N. Alon; A. Hajnal

doi:10.1007/BF01789457

Ramsey graphs contain many distinct induced subgraphs

N. Alon, A. Hajnal

Research output: Contribution to journal › Article › peer-review

5 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 language	English (US)
Pages (from-to)	1-6
Number of pages	6
Journal	Graphs and Combinatorics
Volume	7
Issue number	1
DOIs	https://doi.org/10.1007/BF01789457
State	Published - Mar 1991
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1007/BF01789457

Cite this

@article{57de0d028cba401a82cec45758435214,

title = "Ramsey graphs contain many distinct induced subgraphs",

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.",

author = "N. Alon and A. Hajnal",

year = "1991",

month = mar,

doi = "10.1007/BF01789457",

language = "English (US)",

volume = "7",

pages = "1--6",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "1",

}

TY - JOUR

T1 - Ramsey graphs contain many distinct induced subgraphs

AU - Alon, N.

AU - Hajnal, A.

PY - 1991/3

Y1 - 1991/3

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0040197124&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0040197124&partnerID=8YFLogxK

U2 - 10.1007/BF01789457

DO - 10.1007/BF01789457

M3 - Article

AN - SCOPUS:0040197124

SN - 0911-0119

VL - 7

SP - 1

EP - 6

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 1

ER -

Ramsey graphs contain many distinct induced subgraphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this