✦ LIBER ✦

Graphs with a small number of distinct induced subgraphs

✍ Scribed by Noga Alon; Béla Bollobás

Publisher: Elsevier Science
Year: 1989
Tongue: English
Weight: 514 KB
Volume: 75
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(89)90074-5

No coin nor oath required. For personal study only.

✦ Synopsis

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 &II', where E < lo-*', then either G or its complement contain an independent set on at least (1 -4e)n vertices. This settles a problem of Erdiis and Hajnal.

📜 SIMILAR VOLUMES

On the number of distinct induced subgra

On the number of distinct induced subgraphs of a graph

✍ P. Erdős; A. Hajnal 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 582 KB

On the number of induced subgraphs of a

On the number of induced subgraphs of a random graph

✍ Hiroshi Maehara 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 175 KB

2-Colorings of complete graphs with a sm

2-Colorings of complete graphs with a small number of monochromatic K4 subgraphs

✍ F. Franek; V. Rödl 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 318 KB

Extremal graphs with bounded densities o

Extremal graphs with bounded densities of small subgraphs

✍ Griggs, Jerrold R.; Simonovits, Mikl�os; Thomas, George Rubin 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 373 KB 👁 1 views

Let Ex(n, k, µ) denote the maximum number of edges of an n-vertex graph in which every subgraph of k vertices has at most µ edges. Here we summarize some known results of the problem of determining Ex(n, k, µ), give simple proofs, and find some new estimates and extremal graphs. Besides proving new

On the Density of Subgraphs in a Graph w

On the Density of Subgraphs in a Graph with Bounded Independence Number

✍ Pavel Valtr 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 260 KB

Let \_(n, m, k) be the largest number \_ # [0, 1] such that any graph on n vertices with independence number at most m has a subgraph on k vertices with at lest \_ } ( k 2 ) edges. Up to a constant multiplicative factor, we determine \_(n, m, k) for all n, m, k. For log n m=k n, our result gives \_(

On the number of maximal bipartite subgr

On the number of maximal bipartite subgraphs of a graph

✍ Jesper Makholm Byskov; Bolette Ammitzbøll Madsen; Bjarke Skjernaa 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 72 KB 👁 2 views

We show new lower and upper bounds on the maximum number of maximal induced bipartite subgraphs of graphs with n vertices. We present an infinite family of graphs having 105 n=10 % 1:5926 n ; such subgraphs show an upper bound of O(12 n=4 ) ¼ O(1:8613 n ) and give an algorithm that finds all maximal