On the complexity of partitioning graphs into connected subgraphs (Q1057062): Difference between revisions

k-partition of a finite set X is a partition \(X=X_ 1\cup...\cup X_ p\) where \(| X_ i| =k\) for \(i=1,...,p\). For a graph property \(\pi\), define \(\pi\)-k-partition to be one in which each subset induces a graph with property \(\pi\). The abbreviation Vk(\(\pi)\) (resp. Ek(\(\pi)\)) denotes the problem of deciding whether a graph has a \(\pi\)-k-partition of its vertices (resp. edges). The main result states that for any fixed \(k\geq 3\) all the following five problems: Vk (connected), Vk (tree), VK (path), Ek (connected), Ek (path) are NP-complete for planar bipartite graphs. Besides, some similar results on NP-completeness of problems of kind \(Vm_ k\) (resp. \(Em_ k)\) with increasing \(m_ k\) are ascertained.