Partitioning into degenerate graphs in linear time

DOI10.1016/J.EJC.2023.103771zbMATH Open1525.05154arXiv2204.11100OpenAlexW4385823801MaRDI QIDQ6080366FDOQ6080366

Author name not available (Why is that?)

Publication date: 2 October 2023

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The \(m\)-degenerate chromatic number of a digraph
• Three short proofs in graph theory
• An Efficient Parallel Biconnectivity Algorithm
• Variable degeneracy: Extensions of Brooks' and Gallai's theorems
• Fast randomized algorithms for distributed edge coloring
• Optimal Vertex Partitions
• Partitioning a graph into degenerate subgraphs
• Vertex partitions and maximum degenerate subgraphs
• Vertex partition of hypergraphs and maximum degenerate subhypergraphs
• Digraphs and Variable Degeneracy
• Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration

Cited In (2)

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

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)