##
**Zentralblatt MATH**

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

**Zbl.No: ** 493.05049

**Autor: ** Erdös, Paul; Hobbs, Arthur M.; Payan, C.

**Title: ** Disjoint cliques and disjoint maximal independent sets of vertices in graphs. (In English)

**Source: ** Discrete Math. 42, 57-61 (1982).

**Review: ** From the authors' summary: ``In this paper, we find lower bounds for the maximum and minimum numbers of cliques in maximal sets of pairwise disjoint cliques in a graph.By complementation, these yield lower bounds for the maximum and minimum numbers of independent sets in maximal sets of pairwise sisjoint maximal independent sets of vertices in a graph. In the latter context, we show by examples that one of our bounds is best possible.'' Further, the authors show that Berge's [unpublished] and C. Pajan's hypotheses [Thesis, Grenoble, 1977], which state that any regular graph has two disjoint maximal independent sets of vertices, are true for any regular graph with n vertices and degree n-k, where k < -2+2\sqrt{2n}.

**Reviewer: ** M.Sudolský

**Classif.: ** * 05C70 Factorization, etc.

05C35 Extremal problems (graph theory)

**Keywords: ** maximal sets of cliques; regular graph; maximal independent sets

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag