## 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