Partition planar graph into connected subgraphs of equal size
For a graph $G=(V,E)$, deciding if $V$ can be partitioned into equal sized subsets (say, for a fixed size $r$) where each subset induces a connected subgraph is $\mathsf{NP}$-hard. It remains $\mathsf{NP}$-hard for planar graphs, and also if the number of subsets is fixed instead of the subset size ($|V|/r$ fixed).

However, the problem is polynomial for cycles, and thus for Hamiltonian graphs. It is also polynomial for trees and for series-parallel graphs when the number of subsets is fixed.

You can find these results in:


M. E. Dyer and A. M. Frieze. On the complexity of partitioning graphs into connected subgraphs.  Discrete Applied Mathematics, 10(2), 139-153. 1985.
N. Apollonio &amp; al. Bicolored graph partitioning, or: gerrymandering at its worst.  Discrete Applied Mathematics, 157(17), 3601-3614. 2009.


Edit (bis): I think that I was wrong about Hamiltonian graphs. They may be partitioned even if their Hamiltonian cycle cannot. Thus the problem can be not polynomial. See the first comment.