We prove that for any additive hereditary property P > O, it is NP-hard to decide if a given graph G allows a vertex partition V(G) = A∪B such that G[A] ∈ 𝓞 (i.e., A is independent) and G[B] ∈ P.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1052,
author = {Jan Kratochv\'\i l and Ingo Schiermeyer},
title = {On the computational complexity of (O,P)-partition problems},
journal = {Discussiones Mathematicae Graph Theory},
volume = {17},
year = {1997},
pages = {253-258},
zbl = {0904.05074},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1052}
}
Jan Kratochvíl; Ingo Schiermeyer. On the computational complexity of (O,P)-partition problems. Discussiones Mathematicae Graph Theory, Tome 17 (1997) pp. 253-258. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1052/
[000] [1] M.R. Garey and D.S. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, New York, 1979. | Zbl 0411.68039
[001] [2] J. Bucko, M. Frick, P. Mihok and R. Vasky, Uniquely partitionable graphs, Discussiones Mathematicae Graph Theory 17 (1997) 103-113. | Zbl 0906.05057
[002] [3] P. Mihók, G. Semanišin, Additive hereditary properties are uniquely factorizable, Czecho-Slovak Conference on Combinatorics and Graph Theory, Chudenice, 1997.