  An independent set A is maximal if it is not a proper subset of an
independent set, while A is maximum if it has a maximum size. The problem of
whether a graph has a pair of disjoint maximal independent sets was introduced
by C. Berge in early 70's. The class of graphs for which every induced subgraph
admits two disjoint maximal independent sets was characterized in (Shaudt,
2015). It is known that deciding whether a graph has two disjoint maximal
independent sets is a NP-complete problem (Henning et al., 2009). In this
paper, we are focused on finding conditions ensuring the existence of two
disjoint maximum independent sets.
