Stable sets versus independent sets (Q686148): Difference between revisions

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.