# Dividing a graph into $k$ subgraphs

Is there an algorithm for finding the number of ways a given connected graph can be divided into $k$ connected subgraphs? I've searched the Web for an answer, but perhaps I'm using the wrong words as my graph theory is rusty. Basically, given a set of vertices, I'm looking for the number of ways this set can be split into $k$ disjoint subsets, where each subset of vertices is connected.

With the graph example above and $k=3$, a possible division would be {A, B, D}, {C, F, H} and {E, G}. An example of a disallowed subset would be {A, F} as they are not directly connected.

EDIT

Suppose I narrowed the scope to a grid graph like the one below:

Would that help find an algorithm?

• Are you interested in an actually feasible algorithm to run it on a computer or for theoretic purpose? – M. Winter May 22 '17 at 8:50
• @M. Winter: I'm looking for an algorithm to run on a computer, but if you have a more theoretic answer, that would also be welcome. – Jens May 22 '17 at 15:35
• Without any restrictions I would just suggest the exhaustive search. That of course is no option for a real program. – M. Winter May 23 '17 at 8:19