# On the computational complexity of (O,P)-partition problems

Jan Kratochvíl; Ingo Schiermeyer

Discussiones Mathematicae Graph Theory (1997)

- Volume: 17, Issue: 2, page 253-258
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topJan Kratochvíl, and Ingo Schiermeyer. "On the computational complexity of (O,P)-partition problems." Discussiones Mathematicae Graph Theory 17.2 (1997): 253-258. <http://eudml.org/doc/270382>.

@article{JanKratochvíl1997,

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.},

author = {Jan Kratochvíl, Ingo Schiermeyer},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {computational complexity; graph properties; partition problems; additive hereditary graph properties},

language = {eng},

number = {2},

pages = {253-258},

title = {On the computational complexity of (O,P)-partition problems},

url = {http://eudml.org/doc/270382},

volume = {17},

year = {1997},

}

TY - JOUR

AU - Jan Kratochvíl

AU - Ingo Schiermeyer

TI - On the computational complexity of (O,P)-partition problems

JO - Discussiones Mathematicae Graph Theory

PY - 1997

VL - 17

IS - 2

SP - 253

EP - 258

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

LA - eng

KW - computational complexity; graph properties; partition problems; additive hereditary graph properties

UR - http://eudml.org/doc/270382

ER -

## References

top- [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. Zbl0411.68039
- [2] J. Bucko, M. Frick, P. Mihok and R. Vasky, Uniquely partitionable graphs, Discussiones Mathematicae Graph Theory 17 (1997) 103-113. Zbl0906.05057
- [3] P. Mihók, G. Semanišin, Additive hereditary properties are uniquely factorizable, Czecho-Slovak Conference on Combinatorics and Graph Theory, Chudenice, 1997.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.