DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory  17(2) (1997) 253-258
DOI: 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.