A set and collection lemma

MaRDI QIDQ405128zbMATH OpenFDO

Authors Vadim E. Levit, Eugen Mandrescu

Publication date 4 September 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1101.4564, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i1p40

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

matchingcoronacorecliqueindependent setstable set

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial inequalities (05A20)

Abstract: A set S is independent if no two vertices from S are adjacent. In this paper we prove that if F is a collection of maximum independent sets of a graph, then there is a matching from S-{intersection of all members of F} into {union of all members of F}-S, for every independent set S. Based on this finding we give alternative proofs for a number of well-known lemmata, as the "Maximum Stable Set Lemma" due to Claude Berge and the "Clique Collection Lemma" due to Andr'as Hajnal.

Recommendations

• On the number of maximum independent sets of graphs
• Monotonic properties of collections of maximum independent sets of a graph
• On König-Egerváry collections of maximum critical independent sets
• scientific article; zbMATH DE number 3880761
• scientific article; zbMATH DE number 20270

Cites work

• scientific article; zbMATH DE number 3900787 (Why is no real title available?)
• scientific article; zbMATH DE number 3732108 (Why is no real title available?)
• scientific article; zbMATH DE number 1472162 (Why is no real title available?)
• A Theorem on k-Saturated Graphs
• A characterization of the graphs in which the transversal number equals the matching number
• A note on hitting maximum and maximal cliques with a stable set
• Combinatorial properties of the family of maximum stable sets of a graph
• Hitting all maximum cliques with a stable set using lopsided independent transversals
• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• On \(\alpha\)-critical edges in König--Egerváry graphs
• On hitting all maximum cliques with an independent set
• On the number of vertices belonging to all maximum stable sets of a graph
• Very well covered graphs

Cited in

(10)

• Two more characterizations of König-Egerváry graphs
• On an annihilation number conjecture
• On König-Egerváry collections of maximum critical independent sets
• On some conjectures concerning critical independent sets of a graph
• Matchings in graphs and groups
• Linear maps on nonnegative symmetric matrices preserving the independence number
• scientific article; zbMATH DE number 819294 (Why is no real title available?)
• Critical and maximum independent sets of a graph
• On the intersection of all critical sets of a unicyclic graph
• Monotonic properties of collections of maximum independent sets of a graph

This page was built for publication: A set and collection lemma

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q405128)