✦ LIBER ✦

Induced subgraphs of prescribed size

✍ Scribed by Noga Alon; Michael Krivelevich; Benny Sudakov

Publisher: John Wiley and Sons
Year: 2003
Tongue: English
Weight: 127 KB
Volume: 43
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10117

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A subgraph of a graph G is called trivial if it is either a clique or an independent set. Let q(G) denote the maximum number of vertices in a trivial subgraph of G. Motivated by an open problem of Erdős and McKay we show that every graph G on n vertices for which q(G)≤ C log n contains an induced subgraph with exactly y edges, for every y between 0 and n^δ (C)^. Our methods enable us also to show that under much weaker assumption, i.e., q(G) ≤ n/14, G still must contain an induced subgraph with exactly y edges, for every y between 0 and $e^{\Omega} (\sqrt { \log, n})$. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 239–251, 2003

📜 SIMILAR VOLUMES

On induced subgraphs of a block

✍ Ladislav Nebeský 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 271 KB

If G is a block, then a vertex u of G is called critical if Gu is not a block. In this article, relationships between the localization of critical vertices and the localization of vertices of relatively small degrees (especially, of degree two) are studied. A block is called semicritical if a) each

Random Induced Subgraphs of Generalizedn

Random Induced Subgraphs of Generalizedn-Cubes

✍ Christian M. Reidys 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 312 KB

vertices are adjacent if they differ in exactly one coordinate. Random induced subgraphs, . with probability . The first theorem shows that for s c ln n rn there exists n n a unique largest component in ⌫ -Q Q n which contains almost all vertices and that n ␣ Ž . the size of the second largest comp

Forbidden induced subgraph characterizat

Forbidden induced subgraph characterization of cograph contractions

✍ Igor Ed. Zverovich; Inessa I. Zverovich 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 101 KB

Let S 1 ; S 2 ; . . . ; S t be pairwise disjoint non-empty stable sets in a graph H. The graph H Ã is obtained from H by: (i) replacing each S i by a new vertex q i ; (ii) joining each q i and q j , 1 i 6 ¼ j t, and; (iii) joining q i to all vertices in HÀ(S 1 [ S 2 [ Á Á Á [ S t ) which were adjace

Finite Induced Graph Ramsey Theory: On P

Finite Induced Graph Ramsey Theory: On Partitions of Subgraphs

✍ D.S. Gunderson; V. Rodl; N.W. Sauer 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 425 KB

For given finite (unordered) graphs $G$ and $H$, we examine the existence of a Ramsey graph $F$ for which the strong Ramsey arrow $F \rightarrow(G)_{r}^{\prime \prime}$ holds. We concentrate on the situation when $H$ is not a complete graph. The set of graphs $G$ for which there exists a

Forbidden subgraphs and bounds on the si

Forbidden subgraphs and bounds on the size of a maximum matching

✍ Michael D. Plummer; Akira Saito 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 126 KB 👁 1 views

## Abstract Let __K__~1,__n__~ denote the star on __n__ + 1 vertices; that is, __K__~1,__n__~ is the complete bipartite graph having one vertex in the first vertex class of its bipartition and __n__ in the second. The special graph __K__~1,3~, called the __claw__, has received much attention in the

A semi-induced subgraph characterization

A semi-induced subgraph characterization of upper domination perfect graphs

✍ Zverovich, Igor E.; Zverovich, Vadim E. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 324 KB 👁 2 views

Let β(G) and Γ(G) be the independence number and the upper domination number of a graph G, respectively. A graph G is called Γ-perfect if β(H) = Γ(H), for every induced subgraph H of G. The class of Γ-perfect graphs generalizes such well-known classes of graphs as strongly perfect graphs, absorbantl