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