Stable sets versus independent sets

DOI10.1016/0012-365X(93)90325-NMaRDI QIDQ686148zbMATH OpenOpenAlexFDO

Authors Guoli Ding

Publication date 10 March 1994

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(93)90325-n

zbMATH Keywords

independent setsmatroidal numbermatroidsNP-hardstable sets

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Structural characterization of families of graphs (05C75) Analysis of algorithms and problem complexity (68Q25)

Review text

The matroidal number \(m(G)\) of a graph \(G\) is defined as the smallest integer \(m\) so that the collection of the stable sets of \(G\) arises as \(I_ 1\cup I_ 2 \cup \cdots \cup I_ m\) where the \(I_ i\) are collections of independent sets of matroids on the vertex set of \(G\). Computing \(m(G)\) is shown to be NP-hard and various results on graphs of matroidal number at most \(m\) are given. Similar problems with ``intersection rather than ``union are also considered.

Recommendations

• scientific article; zbMATH DE number 4187860
• scientific article; zbMATH DE number 6266
• scientific article; zbMATH DE number 3150
• scientific article; zbMATH DE number 4139804
• On the number of vertices belonging to all maximum stable sets of a graph

Cites work

• Boolean techniques for matroidal decomposition of independence systems and applications to graphs
• scientific article; zbMATH DE number 3856849 (Why is no real title available?)
• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Matroids and the greedy algorithm
• Ordering by Divisibility in Abstract Algebras
• Subgraphs and well‐quasi‐ordering
• The NP-Completeness of Edge-Coloring

Cited in

(8)

• Stable multi-sets
• Matrix formulation of EISs of graphs and its application to WSN covering problems
• Two forbidden induced subgraphs and well-quasi-ordering
• scientific article; zbMATH DE number 4139804 (Why is no real title available?)
• scientific article; zbMATH DE number 6266 (Why is no real title available?)
• scientific article; zbMATH DE number 4187860 (Why is no real title available?)
• Canonical antichains of unit interval and bipartite permutation graphs
• Labelled induced subgraphs and well-quasi-ordering

This page was built for publication: Stable sets versus independent sets

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