DMGT

Discussiones Mathematicae Graph Theory 17(2) (1997) 253-258
DOI: https://doi.org/10.7151/dmgt.1052

ON THE COMPUTATIONAL COMPLEXITY OF ( O, P)-PARTITION PROBLEMS

Jan Kratochvíl

Department of Applied Mathematics
Charles University, Prague, Czech Republic
e-mail: honza@kam.ms.mff.cuni.cz

Ingo Schiermeyer

Lehrstuhl für Diskrete Mathematik, und Grundlagen der Informatik
Technische Universität Cottbus, D-03013 Cottbus, Germany
e-mail: schierme@math.tu-cottbus.de

Abstract

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] ∈ O (i.e., A is independent) and G[B] ∈ P.

Keywords: computational complexity, graph properties, partition problems.

1991 Mathematics Subject Classifications: 05C75, 68Q15, 68R10.

References

[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]	P. Mihók, The Structure of Hereditary Properties of Graphs and Minimal Reducible Bounds, DIMATIA-DIMACS conference on Discrete Mathematics, Sti rín, 1997.
[3]	P. Mihók, G. Semanišin, Additive hereditary properties are uniquely factorizable, Czecho-Slovak Conference on Combinatorics and Graph Theory, Chudenice, 1997.