TY - JOUR
T1 - Graphs with a Small Number of Distinct Induced Subgraphs
AU - Alon, Noga
AU - Bollobás, Béla
N1 - Funding Information:
Fund for Basic Research Administered by the Israel Academy of Sciences. t Research supported in part by NSF Grant DMS 8806097.
Funding Information:
* Research supported in part by Allon Fellowship, by a Bat-Sheva de Rothschild grant and by the
PY - 1989/1/1
Y1 - 1989/1/1
N2 - 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 Erdõs and Hajnal.
AB - 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 Erdõs and Hajnal.
UR - http://www.scopus.com/inward/record.url?scp=77957099268&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77957099268&partnerID=8YFLogxK
U2 - 10.1016/S0167-5060(08)70562-4
DO - 10.1016/S0167-5060(08)70562-4
M3 - Article
AN - SCOPUS:77957099268
SN - 0167-5060
VL - 43
SP - 23
EP - 30
JO - Annals of Discrete Mathematics
JF - Annals of Discrete Mathematics
IS - C
ER -