On disjoint maximal independent sets in graphs

As a second result, we show the following: the computation of two disjoint maximal independent sets of minimum total size, NP-hard for general graphs, can be done in linear time on trees.