Stable sets versus independent sets
type: Item
instance of: scholarly article
title: Stable sets versus independent sets
zbMATH Open document ID: 0783.05036
DOI: 10.1016/0012-365X(93)90325-N
author: Guoli Ding
published in: Discrete Mathematics
publication date: 1994-03-10T00:00:00Z
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.
reviewed by: András Recski
Mathematics Subject Classification ID: 05B35
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 427998
zbMATH Keywords: matroidal number
zbMATH Keywords: stable sets
zbMATH Keywords: independent sets
zbMATH Keywords: matroids
zbMATH Keywords: NP-hard
MaRDI profile type: Publication
cites work: Boolean techniques for matroidal decomposition of independence systems and applications to graphs
cites work: Q3325492
cites work: Subgraphs and well‐quasi‐ordering
cites work: Q4198056
cites work: Matroids and the greedy algorithm
cites work: Ordering by Divisibility in Abstract Algebras
cites work: The NP-Completeness of Edge-Coloring
cites work: Q4111952
full work available at URL: 0012-365x(93)90325-n
OpenAlex ID: W2068255817
description: scientific article; zbMATH DE number 427998