Résumé
An (r,)-partition of a graph G is a partition of its vertex set into r independent sets and cliques. A graph is (r,) if it admits an (r,)-partition. A graph is well-covered if every maximal independent set is also maximum. A graph is (r,)-well-covered if it is both (r,) and well-covered. In this paper we consider two different decision problems. In the (r,)-Well-Covered Graph problem ((r,)wc-g for short), we are given a graph G, and the question is whether G is an (r,)-well-covered graph. In the Well-Covered (r,)-Graph problem (wc-(r,)g for short), we are given an (r,)-graph G together with an (r,)partition, and the question is whether G is well-covered. This generates two infinite families of problems, for any fixed non-negative integers r and , which we classify as being P, coNP-complete, NP-complete, NP-hard, or coNP-hard. Only the cases wc-(r, 0)g for r ≥ 3 remain open. In addition, we consider the parameterized complexity of these problems for several choices of parameters, such as the size α of a maximum independent set of the input graph, its neighborhood diversity, its clique-width, or the number of cliques in an (r,)-partition. In particular, we show that the parameterized problem of determining whether every maximal independent set of an input graph G has cardinality equal to k can be reduced to the wc-(0,)g problem parameterized by. In addition, we prove that both problems are coW[2]-hard but can be solved in XP-time.