##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 587.05032

**Autor: ** Erdös, Paul; Pach, János

**Title: ** Remarks on stars and independent sets. (In English)

**Source: ** Aspects of topology, Mem. H. Dowker, Lond. Math. Soc. Lect. Note Ser. 93, 307-313 (1985).

**Review: ** [For the entire collection see Zbl 546.00024.]

A graph G has property I_{k} if every set of k independent vertices have a common neighbour; G has property I if it has property I_{k} for all k. Pach, proving a conjecture of Erdös and Fajtolowicz, has shown that theorem 1: Every triangle-free graph on n vertices and having property I, contains a vertex of valency at least (n+1)/3; if 3|(n+1), this result is best possible. Lemma: If every set of \lceil log n\rceil independent vertices of a triangle-free graph on n vertices have a common neighbour, then the graph has property I. Sharpening theorem 1, the authors prove theorem 4: Every triangle-free graph on n vertices and with property I_{\lceil log n\rceil} has a vertex of degree at least (n+1)/3.

Theorem 2: Let f_{r}(n) denote the maximum integer such that every graph on n vertices having property I has a vertex of degree \geq f. Then f_{I}(n) = (1+o(1))\frac{n log log n}{log n}.

Theorem 3. Let f_{I}(r,n) denote the maximum integer f such that every K_{r}-free graph on n vertices having property I has a vertex of degree at least f. Then f_{I}(w(n) log n,n) \leq (2+o(1))\frac{n log log w(n)}{log w(n)}, where w(n) is an arbitrary function tending to infinity.

**Reviewer: ** W.G.Brown

**Classif.: ** * 05C35 Extremal problems (graph theory)

**Keywords: ** extremal graph; independent vertices

**Citations: ** Zbl 546.00024

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag