ArticleOriginal scientific text
Title
On the computational complexity of (O,P)-partition problems
Authors 1, 2
Affiliations
- Department of Applied Mathematics, Charles University
- Lehrstuhl für Diskrete Mathematik, und Grundlagen der Informatik, Technische Universität Cottbus
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] ∈ (i.e., A is independent) and G[B] ∈ P.
Keywords
computational complexity, graph properties, partition problems
Bibliography
- 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.
- J. Bucko, M. Frick, P. Mihok and R. Vasky, Uniquely partitionable graphs, Discussiones Mathematicae Graph Theory 17 (1997) 103-113.
- P. Mihók, G. Semanišin, Additive hereditary properties are uniquely factorizable, Czecho-Slovak Conference on Combinatorics and Graph Theory, Chudenice, 1997.
Pages:
253-258
Main language of publication
English
Received
1997-06-05
Published
1997
Exact and natural sciences