A set and collection lemma
type: Item
instance of: scholarly article
title: A set and collection lemma
zbMATH Open document ID: 1300.05230
author: Vadim E. Levit
author: Eugen Mandrescu
published in: The Electronic Journal of Combinatorics
publication date: 2014-09-04T00:00:00Z
full work available at URL: https://arxiv.org/abs/1101.4564
full work available at URL: v21i1p40
review text: Summary: A set \(S\subseteq V(G)\) is independent if no two vertices from \(S\)~are adjacent. Let \(\alpha\left( G\right) \) stand for the cardinality of a largest independent set.{ }In this paper we prove that if \(\Lambda\) is a nonempty collection of maximum independent sets of a graph \(G\), and \(S\) is an independent set, then there is a matching from \(S-\bigcap\Lambda\) into \(\bigcup\Lambda-S\), and \(\left| S\right| +\alpha(G)\leq\left| \bigcap\Lambda\cap S\right| +\left| \bigcup\Lambda\cup S\right| \). Based on these findings we provide alternative proofs for a number of~well-known lemmata, such as the maximum stable set lemma due to \textit{C. Berge} [Graphs. Amsterdam-New York-Oxford: North-Holland (1985; Zbl 0566.05001)] and the clique collection lemma due to \textit{A. Hajnal} [Can. J. Math. 17, 720--724 (1965; Zbl 0129.39901)].
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05A20
zbMATH DE Number: 6340138
zbMATH Keywords: matching
zbMATH Keywords: independent set
zbMATH Keywords: stable set
zbMATH Keywords: core
zbMATH Keywords: corona
zbMATH Keywords: clique
MaRDI profile type: Publication
arXiv ID: 1101.4564
cites work: Q3919752
cites work: Q3679215
cites work: On the number of vertices belonging to all maximum stable sets of a graph
cites work: A Note on Hitting Maximum and Maximal Cliques With a Stable Set
cites work: Independence numbers of graphs - an extension of the Koenig-Egervary theorem
cites work: Very well covered graphs
cites work: A Theorem on k-Saturated Graphs
cites work: Hitting all maximum cliques with a stable set using lopsided independent transversals
cites work: Q4489216
cites work: Combinatorial properties of the family of maximum stable sets of a graph
cites work: On \(\alpha\)-critical edges in König--Egerváry graphs
cites work: On hitting all maximum cliques with an independent set
cites work: A characterization of the graphs in which the transversal number equals the matching number
description: scientific article; zbMATH DE number 6340138