Partitioning into degenerate graphs in linear time

DOI10.1016/J.EJC.2023.103771MaRDI QIDQ6080366zbMATH OpenOpenAlexFDO

Authors

Publication date 2 October 2023

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2204.11100

zbMATH Keywords

NP-completenessBrooks' theoreminduced forest 2-partition problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Vertex degrees (05C07) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Let $G$ be a connected graph with maximum degree $Deltageq3$ 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}geqDelta-s$, then $G$ admits a vertex partition into parts $A_1,dots,A_s$ such that, for $1leqileqs$, $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.

Recommendations

• Partitioning a graph into degenerate subgraphs
• Vertex partitions and maximum degenerate subgraphs
• Partitioning into graphs with only small components
• Vertex partition of hypergraphs and maximum degenerate subhypergraphs
• Fast algorithm of equitably partitioning degenerate graphs into graphs with lower degeneracy

Cites work

• scientific article; zbMATH DE number 3661375 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• An Efficient Parallel Biconnectivity Algorithm
• Digraphs and variable degeneracy
• Fast randomized algorithms for distributed edge coloring (extended abstract)
• Optimal Vertex Partitions
• Partitioning a graph into degenerate subgraphs
• Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration
• The \(m\)-degenerate chromatic number of a digraph
• Three short proofs in graph theory
• Variable degeneracy: Extensions of Brooks' and Gallai's theorems
• Vertex partition of hypergraphs and maximum degenerate subhypergraphs
• Vertex partitions and maximum degenerate subgraphs

Cited in

(2)

• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• A linear time algorithm for graph partition problems

This page was built for publication: Partitioning into degenerate graphs in linear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6080366)