9

An independent set that disconnects its graph is called an "independent cut", graphs that contain an independent cut are called "fragile graphs", and recognizing fragile graphs is known NP-complete [C. deFigueiredo, S. Klein, "NP-completeness of multipartite cutset testing", Congr. Numer. 119 (1996) 217–222, as cited by Guantao ...


Only top voted, non community-wiki answers of a minimum length are eligible