A note on the computational complexity of graph vertex partition ?
A stable set of a graph is a vertex set in which any two vertices are not adjacent. It was proven in [A. Brandstdt, V.B. Le, T. Szymczak, The complexity of some problems related to graph 3-colorability, Discrete Appl. Math. 89 (1998) 5973] that the following problem is NP-complete: Given a bipartite graph G, check whether G has a stable set S such that G-S G - S is a tree. In this paper we prove the following problem is polynomially solvable: Given a graph G with maximum degree 3 and containing no vertices of degree 2, check whether G has a stable set S such that G-S G - S is a tree. Thus we partly answer a question posed by the authors in the above paper. Moreover, we give some structural characterizations for a graph G with maximum degree 3 that has a stable set S  such that G-S G - S is a tree.
stable set graph partition deficiency number polynomial algorithm xuong tree