Graphs with a small number of distinct induced subgraphs

Noga Alon; Béla Bollobás

doi:10.1016/0012-365X(89)90074-5

Graphs with a small number of distinct induced subgraphs

Noga Alon, Béla Bollobás

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

18 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^-21, then either G or its complement contain an independent set on at least (1-4ε)n vertices. This settles a problem of Erdős and Hajnal.

Original language	English (US)
Pages (from-to)	23-30
Number of pages	8
Journal	Discrete Mathematics
Volume	75
Issue number	1-3
DOIs	https://doi.org/10.1016/0012-365X(89)90074-5
State	Published - May 1989
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/0012-365X(89)90074-5

Cite this

@article{751ee5f5094445289682698bb17d7605,

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

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

note = "Funding Information: * Research supported Fund for Basic Research t Research supported",

year = "1989",

month = may,

doi = "10.1016/0012-365X(89)90074-5",

language = "English (US)",

volume = "75",

pages = "23--30",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "1-3",

}

TY - JOUR

T1 - Graphs with a small number of distinct induced subgraphs

AU - Alon, Noga

AU - Bollobás, Béla

N1 - Funding Information: * Research supported Fund for Basic Research t Research supported

PY - 1989/5

Y1 - 1989/5

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 Erdő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 Erdős and Hajnal.

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

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

U2 - 10.1016/0012-365X(89)90074-5

DO - 10.1016/0012-365X(89)90074-5

M3 - Article

AN - SCOPUS:38249023707

SN - 0012-365X

VL - 75

SP - 23

EP - 30

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

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