Recognizing maximal unfrozen graphs with respect to independent sets is CO-NP-complete.
Abbas, N. ; Culberson, J. ; Stewart, L.
Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only], Tome 7 (2005), p. 141-153 / Harvested from The Electronic Library of Mathematics
Access to full text
Full (PDF)
Publié le : 2005-01-01
EUDML-ID : urn:eudml:doc:129518 
@article{05279353,
     title = {Recognizing maximal unfrozen graphs with respect to independent sets is CO-NP-complete.},
     journal = {Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]},
     volume = {7},
     year = {2005},
     pages = {141-153},
     zbl = {1153.05322},
     language = {en},
     url = {http://dml.mathdoc.fr/item/05279353}
}

Abbas, N.; Culberson, J.; Stewart, L. Recognizing maximal unfrozen graphs with respect to independent sets is CO-NP-complete.. Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only], Tome 7 (2005) pp. 141-153. http://gdmltest.u-ga.fr/item/05279353/