Geodesic
On the computational complexity of (O,P)-partition problems
Discussiones Mathematicae. Graph Theory, Tome 17 (1997) no. 2, pp. 253-258 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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.
Keywords: computational complexity, graph properties, partition problems 
@article{DMGT_1997_17_2_a3,
     author = {Kratochv{\'\i}l, Jan and Schiermeyer, Ingo},
     title = {On the computational complexity of {(O,P)-partition} problems},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {253--258},
     year = {1997},
     volume = {17},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_1997_17_2_a3/}
}
TY  - JOUR
AU  - Kratochvíl, Jan
AU  - Schiermeyer, Ingo
TI  - On the computational complexity of (O,P)-partition problems
JO  - Discussiones Mathematicae. Graph Theory
PY  - 1997
SP  - 253
EP  - 258
VL  - 17
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_1997_17_2_a3/
LA  - en
ID  - DMGT_1997_17_2_a3
ER  - 
%0 Journal Article
%A Kratochvíl, Jan
%A Schiermeyer, Ingo
%T On the computational complexity of (O,P)-partition problems
%J Discussiones Mathematicae. Graph Theory
%D 1997
%P 253-258
%V 17
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_1997_17_2_a3/
%G en
%F DMGT_1997_17_2_a3
Kratochvíl, Jan; Schiermeyer, Ingo. On the computational complexity of (O,P)-partition problems. Discussiones Mathematicae. Graph Theory, Tome 17 (1997) no. 2, pp. 253-258. http://geodesic.mathdoc.fr/item/DMGT_1997_17_2_a3/

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

[2] J. Bucko, M. Frick, P. Mihok and R. Vasky, Uniquely partitionable graphs, Discussiones Mathematicae Graph Theory 17 (1997) 103-113.

[3] P. Mihók, G. Semanišin, Additive hereditary properties are uniquely factorizable, Czecho-Slovak Conference on Combinatorics and Graph Theory, Chudenice, 1997.