Quadratic-time partition conjecture for noncomplete connected graphs

Let $G$ be a connected graph with maximum degree $k \geq 3$, distinct from $K_{k+1}$. For integers $s \geq 2$ and $p_1,\ldots,p_s \geq 0$ satisfying

$$p_1+\cdots+p_s \geq k-s,$$

a $(p_1,\ldots,p_s)$-partition of $G$ is a partition of $V(G)$ into $s$ parts such that the subgraph induced by the $i$th part has maximum degree at most $p_i$. Quadratic-time partition conjecture. For every such $G$, $s$, and $p_1,\ldots,p_s$, a $(p_1,\ldots,p_s)$-partition of $G$ can be found in $O(n^2)$ time. The preceding proposition establishes the corresponding linear-time result when $G$ is not regular; the conjecture concerns the remaining regular case and is presented as an outstanding case in the paper.