Boolean techniques for matroidal decomposition of independence systems and applications to graphs

AbstractThe problem of decomposing an independence system into the set-theoretic union of matroids is considered in the first part of this paper and a Boolean procedure is proposed for finding the prime matroidal components of such a decomposition. The second part of the paper deals with the special case of the independence system of all stable sets of a graph, characterizes the graphs whose family of stable sets is the set-theoretic union of two matroids, produces a class of perfect graphs of matroidal number k and gives for graphs an accelerated version of the general decomposition technique