Partitioning into degenerate graphs in linear time

DOI10.1016/j.ejc.2023.103771zbMath1525.05154arXiv2204.11100OpenAlexW4385823801MaRDI QIDQ6080366

No author found.

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) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Connectivity (05C40) Vertex degrees (05C07)

Cites Work

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

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