New answers tagged


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 ...

Top 50 recent answers are included