A set and collection lemma

zbMATH Open1300.05230arXiv1101.4564MaRDI QIDQ405128FDOQ405128

Authors: Vadim E. Levit, Eugen Mandrescu 

Publication date: 4 September 2014

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

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.

Full work available at URL: https://arxiv.org/abs/1101.4564

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

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

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)

Cites Work

• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• Combinatorial properties of the family of maximum stable sets of a graph
• Very well covered graphs
• A characterization of the graphs in which the transversal number equals the matching number
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the number of vertices belonging to all maximum stable sets of a graph
• On \(\alpha\)-critical edges in König--Egerváry graphs
• On hitting all maximum cliques with an independent set
• Hitting all maximum cliques with a stable set using lopsided independent transversals
• A note on hitting maximum and maximal cliques with a stable set
• A Theorem on k-Saturated 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
• Linear maps on nonnegative symmetric matrices preserving the independence number
• On some conjectures concerning critical independent sets of a graph
• Matchings in graphs and groups
• Title not available (Why is that?)
• 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)