Partitioning into degenerate graphs in linear time

Let $G$ be a connected graph with maximum degree $\mathrm{\Delta }\ge 3$ distinct from $K_{\mathrm{\Delta }+1}$. Generalizing Brooks’ Theorem, Borodin, Kostochka and Toft proved that if $p_1,\dots ,p_s$ are non-negative integers such that $p_1

• \dots + p_s \geq \Delta - s$,then$G$admitsavertexpartitionintoparts$A_1, \dots, A_s$suchthat,for$1 \leq i \leq s$,$G[A_i]$is$p_i$-degenerate. Here we show that such a partition can be performed in linear time. This generalizes previous results that treated subcases of a conjecture of Abu-Khzam, Feghali and Heggernes~\cite{abu2020partitioning}, which our result settles in full.