Peter MIHÓK
                        (Slovak Academy of Sciences, Koszyce)
 
 

   
 

On the existence of uniquely partitionable graphs  

Let ${\cal P}$ be a property of graphs. A vertex $({\cal P},n)$-partition of a graph $G$ is a partition $\{ V_{1}, V_{2}, \ldots , V_{n}\}$ of its vertex set $V(G)$ into $n$ classes such that each $V_i$ induces a subgraph $G[V_i]$ with property ${\cal P}$. A graph $G$ is said to be uniquely $({\cal P},n)$-partitionable, $n\geq2$, if $G$ has exactly one $({\cal P},n)$-partition. In this talk we present a survey on the existence of uniquely partitionable graphs with respect to induced hereditary properties. Given an additive induced hereditary property ${\cal P}$, we prove that uniquely $({\cal P},n)$-partitionable graphs exist if and only if the property ${\cal 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. 

 

  Serdecznie zapraszamy wszystkich chętnych !