Graphs with a Small Number of Distinct Induced Subgraphs

Noga Alon; Béla Bollobás

doi:10.1016/S0167-5060(08)70562-4

Graphs with a Small Number of Distinct Induced Subgraphs

Noga Alon, Béla Bollobás

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

5 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 εn², where ε < 10⁻²¹, 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.

Original language	English (US)
Pages (from-to)	23-30
Number of pages	8
Journal	Annals of Discrete Mathematics
Volume	43
Issue number	C
DOIs	https://doi.org/10.1016/S0167-5060(08)70562-4
State	Published - Jan 1 1989
Externally published	Yes

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics

Access to Document

10.1016/S0167-5060(08)70562-4

Cite this

@article{f71616226ec647cdbde9f3acd1a521d1,

title = "Graphs with a Small Number of Distinct Induced Subgraphs",

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 Erd{\~o}s and Hajnal.",

author = "Noga Alon and B{\'e}la Bollob{\'a}s",

note = "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",

year = "1989",

month = jan,

day = "1",

doi = "10.1016/S0167-5060(08)70562-4",

language = "English (US)",

volume = "43",

pages = "23--30",

journal = "Annals of Discrete Mathematics",

issn = "0167-5060",

publisher = "Elsevier B.V.",

number = "C",

}

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 - https://www.scopus.com/pages/publications/77957099268

UR - https://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 -

Graphs with a Small Number of Distinct Induced Subgraphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this