Let $G$ be a connected graph with maximum degree $\Delta \geq 3$ distinct from $K_{\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$ admits a vertex partition into parts $A_1, \dots, A_s$ such that, 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.

翻译：设 $G$ 是一个连通的最大度数为 $\Delta \geq 3$ 且不同于 $K_{\Delta + 1}$ 的图。Borodin、Kostochka 和 Toft 推广了 Brooks 定理，证明如果 $p_1,\dots ,p_s$ 是非负整数，且满足 $p_1 + \dots + p_s \geq \Delta - s$，则 $G$ 可由顶点划分为部分 $A_1,\dots ,A_s$，使得 $1 \leq i \leq s$ 时，$G[A_i]$ 是 $p_i$-退化图。我们在此展示这样的划分可以在线性时间内完成。此结果推广了之前处理 Abu-Khzam、Feghali 和 Heggernes 所提出的猜想的子情形的结果~\cite{abu2020partitioning}，而我们的结果完全解决了该猜想。