The naive algorithm takes $O(n^4)$ time, , where $n$ is the number of vertices in the graph, as Stephen Bly explains.

It is possible to determine whether a graph contains a $4$-clique in $O(n^{3.334})$ time.  See https://cs.stackexchange.com/a/18331/755 for a reference to the algorithm.  I suspect their techniques could be extended to solve your problem (e.g., by enumerating all such cliques, and then you could check whether any of them satisfy your partition requirement) in the same running time.  However, a caution: the techniques may be somewhat theoretical.  The asymptotics may mean that their algorithm only becomes faster than naive solutions for large values of $n$.

As a trivial optimization, you can initially delete all vertices whose degree is $<3$, decompose your graph into connected components, and solve the problem separately on each connected component.  You can also [decompose into biconnected components](https://en.wikipedia.org/wiki/Biconnected_component) and solve the problem separately on each biconnected component, since any clique will necessarily be contained in a single biconnected component.  Taking this even further, we can delete a vertex $v$ if $\{p(w) : w \in N(v), p(w) \ne p(v)\}$ is of size 2 or smaller (since each vertex in any clique of the form you want will pass this check), then decompose into biconnected components, and enumerate all 4-cliques of each resulting component.  This optimization might improve your running time in practice, even though it doesn't make any difference to the worst-case asymptotics.