2022/04/23 by Corsini, Timothée, Quentin Deschamps, Carl Feghali +8
Mathematics · #05C15 #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2204.11100
openalex publication_date 2022/04/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a connected graph with maximum degree Δ≥ 3 distinct from KΔ+ 1. Generalizing 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 performed in linear time. This generalizes previous results that treated subcases of a conjecture of Abu-Khzam, Feghali and Heggernes~\citeabu2020partitioning, which our result settles in full.