Partitioning into degenerate graphs in linear time

Timothée Corsini, Quentin Deschamps, Carl Feghali +3

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