论文标题
在线性时间内分配成堕落的图
Partitioning into degenerate graphs in linear time
论文作者
论文摘要
令$ g $为具有最高度$δ\ geq 3 $的连接图，与$ k_ {δ+ 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 Δ- 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] $是$ p_i $ -degenerate。在这里，我们证明可以在线性时间内执行这样的分区。这概括了先前的结果，该结果处理了Abu-Khzam，Feghali和Heggernes〜\ cite {Abu2020-parttioning}的猜想的子案例，我们的结果已完全解决。
Let $G$ be a connected graph with maximum degree $Δ\geq 3$ distinct from $K_{Δ+ 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 Δ- 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.
