Note on maximal split-stable subgraphs

A multigraph G=(V,R∪B)G=(V,R∪B) with red and blue edges is an R/BR/B-split graph if VV is the union of a red and a blue stable set. Gavril has shown that R/BR/B-split graphs yield a common generalization of split graphs and König–Egerváry graphs. Moreover, R/BR/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 NPNP-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 NPNP-hard cases as well as polynomial ones.