Partitioning into degenerate graphs in linear time - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles European Journal of Combinatorics Year : 2023

Partitioning into degenerate graphs in linear time


Let G be a connected graph with maximum degree ∆ ≥ 3 distinct from K∆+1. Generaliz- ing Brooks’ Theorem, Borodin, Kostochka and Toft proved that if p1, . . . , ps are non-negative integers such that p1 +· · ·+ps ≥ ∆−s, then G admits a vertex partition into parts A1, . . . , As such that, for 1 ≤ i ≤ s, G[Ai] is pi-degenerate. Here we show that such a partition can be per- formed in linear time. This generalizes previous results that treated subcases of a conjecture of Abu-Khzam, Feghali and Heggernes [2], which our result settles in full.

Dates and versions

lirmm-03872198 , version 1 (17-10-2023)



Timothée Corsini, Quentin Deschamps, Carl Feghali, Daniel Gonçalves, Hélène Langlois, et al.. Partitioning into degenerate graphs in linear time. European Journal of Combinatorics, 2023, 114, pp.103771. ⟨10.1016/j.ejc.2023.103771⟩. ⟨lirmm-03872198⟩
67 View
3 Download



Gmail Facebook X LinkedIn More