Note on maximal split-stable subgraphs

Fuchs, Bernhard and Faigle, Ulrich and Peis, Britta (2007) Note on maximal split-stable subgraphs.
Published in: Discrete applied mathematics Vol. 155 (15). pp. 2031-2038.


A multigraph G=(V,R∪B) with red and blue edges is an R/B-split graph if V is the union of a red and a blue stable set. Gavril has shown that R/B-split graphs yield a common generalization of split graphs and König–Egerváry graphs. Moreover, R/B-split graphs can be recognized in linear time. In this note, we address the corresponding optimization problem: identify a set of vertices of maximal cardinality that decomposes into a red and a blue stable set. This problem is NP-hard in general. We investigate the complexity of special and related cases (e.g., (anti-)chains in partial orders and stable matroid bases) and exhibit some NP-hard cases as well as polynomial ones.

Download: [img] Postscript - Preprinted Version
Download (326kB) | Preview
Download: [img] PDF - Preprinted Version
Download (176kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2004-478
Depositing User: Prof. Dr. Ulrich Faigle
Date Deposited: 20 Aug 2007 00:00
Last Modified: 19 Dec 2011 09:44