### Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard.

Skip to main content (access key 's'),
Skip to navigation (access key 'n'),
Accessibility information (access key '0')

Back to Simple Search
# Advanced Search

An additive hereditary graph property is a set of graphs, closed under isomorphism and under taking subgraphs and disjoint unions. Let ₁,...,ₙ be additive hereditary graph properties. A graph G has property (₁∘...∘ₙ) if there is a partition (V₁,...,Vₙ) of V(G) into n sets such that, for all i, the induced subgraph $G\left[{V}_{i}\right]$ is in ${}_{i}$. A property is reducible if there are properties , such that = ∘ ; otherwise it is irreducible. Mihók, Semanišin and Vasky [8] gave a factorisation for any additive hereditary...

**Page 1**