  Let $G = (V, E)$ be a connected graph with maximum degree $k\geq 3$ distinct
from $K_{k+1}$. Given integers $s \geq 2$ and $p_1,\ldots,p_s\geq 0$, $G$ is
said to be $(p_1, \dots, p_s)$-partitionable if there exists a partition of $V$
into sets~$V_1,\ldots,V_s$ such that $G[V_i]$ is $p_i$-degenerate for
$i\in\{1,\ldots,s\}$. In this paper, we prove that we can find a $(p_1, \dots,
p_s)$-partition of $G$ in $O(|V| + |E|)$-time whenever $1\geq p_1, \dots, p_s
\geq 0$ and $p_1 + \dots + p_s \geq k - s$. This generalizes a result of Bonamy
et al. (MFCS, 2017) and can be viewed as an algorithmic extension of Brooks'
theorem and several results on vertex arboricity of graphs of bounded maximum
degree.
  We also prove that deciding whether $G$ is $(p, q)$-partitionable is
$\mathbb{NP}$-complete for every $k \geq 5$ and pairs of non-negative integers
$(p, q)$ such that $(p, q) \not = (1, 1)$ and $p + q = k - 3$. This resolves an
open problem of Bonamy et al. (manuscript, 2017). Combined with results of
Borodin, Kostochka and Toft (\emph{Discrete Mathematics}, 2000), Yang and Yuan
(\emph{Discrete Mathematics}, 2006) and Wu, Yuan and Zhao (\emph{Journal of
Mathematical Study}, 1996), it also settles the complexity of deciding whether
a graph with bounded maximum degree can be partitioned into two subgraphs of
prescribed degeneracy.
