On the existence of uniquely partitionable graphs

Let P be a property of graphs. A vertex (P, n)-partition of a graph G is a partition {V1, V2, …, Vn} of its vertex set V(G) into n classes such that each Vi induces a subgraph G[Vi] with property P. A graph G is said to be uniquely (P, n)-partitionable, n ≥ 2, if G has exactly one (P, n)-partition. In this paper, we present a survey on the existence of uniquely partitionable graphs with respect to induced-hereditary properties. Given an additive induced-hereditary property P, we prove that uniquely (P, n)-partitionable graphs exist if and only if the property P is irreducible. In particular, this implies that for every induced-hereditary property with finitely many connected minimal forbidden induced subgraphs there are uniquely partitionable graphs.