Partitioning a graph into degenerate subgraphs

DOI10.1016/J.EJC.2019.103015MaRDI QIDQ2011133zbMATH OpenOpenAlexFDO

Authors Faisal N. Abu-Khzam, Carl Feghali, Pinar Heggernes

Publication date 28 November 2019

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

NP-completenessBrooks' theoreminduced forest 2-partition problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Let $G=(V,E)$ be a connected graph with maximum degree $kgeq3$ distinct from $K_{k+1}$. Given integers $sgeq2$ and $p_1,ldots,p_{s}geq0$, $G$ is said to be $(p_1,dots,p_s)$-partitionable if there exists a partition of $V$ into sets~$V_1,ldots,V_s$ such that $G[V_i]$ is $p_i$-degenerate for $iin1,ldots,s$. In this paper, we prove that we can find a $(p_1,dots,p_s)$-partition of $G$ in $O(|V|+|E|)$-time whenever $1geq{p}_1,dots,p_{s}geq0$ and $p_1+dots+p_{s}geqk-s$. This generalizes a result of Bonamy et al. (MFCS, 2017) and can be viewed as an algorithmic extension of Brooks' theorem and several results on vertex arboricity of graphs of bounded maximum degree. We also prove that deciding whether $G$ is $(p,q)$-partitionable is $mathbbNP$-complete for every $kgeq5$ and pairs of non-negative integers $(p,q)$ such that $(p,q)ot=(1,1)$ and $p+q=k-3$. This resolves an open problem of Bonamy et al. (manuscript, 2017). Combined with results of Borodin, Kostochka and Toft (emph{Discrete Mathematics}, 2000), Yang and Yuan (emph{Discrete Mathematics}, 2006) and Wu, Yuan and Zhao (emph{Journal of Mathematical Study}, 1996), it also settles the complexity of deciding whether a graph with bounded maximum degree can be partitioned into two subgraphs of prescribed degeneracy.

Recommendations

• Vertex partitions and maximum degenerate subgraphs
• Partitioning into graphs with only small components
• Degree-constrained 2-partitions of graphs
• Vertex partition of hypergraphs and maximum degenerate subhypergraphs

Cites work

• scientific article; zbMATH DE number 1189240 (Why is no real title available?)
• scientific article; zbMATH DE number 1263950 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• k-Degenerate Graphs
• A reconfigurations analogue of Brooks' theorem and its consequences
• Critical Point-Arboritic Graphs
• Decomposing a planar graph into an independent set and a 3-degenerate graph
• Decomposing a planar graph into degenerate graphs
• Kempe equivalence of colourings of cubic graphs
• Large induced degenerate subgraphs
• Partition the vertices of a graph into one independent set and one acyclic set
• Three short proofs in graph theory
• Variable degeneracy: Extensions of Brooks' and Gallai's theorems
• Vertex arboricity and maximum degree

Cited in

(11)

• Vertex partitions and maximum degenerate subgraphs
• Vertex partition of hypergraphs and maximum degenerate subhypergraphs
• A Catlin-type theorem for graph partitioning avoiding prescribed subgraphs
• Digraphs and variable degeneracy
• Decomposition of a graph into two disjoint odd subgraphs
• The high order spectrum of a graph and its applications in graph colouring and clique counting
• Decomposing a graph into two subgraphs with prescribed parities of vertex degrees
• Partitions of hypergraphs under variable degeneracy constraints
• Partitioning into degenerate graphs in linear time
• Decomposing degenerate graphs into locally irregular subgraphs
• scientific article; zbMATH DE number 4187858 (Why is no real title available?)

This page was built for publication: Partitioning a graph into degenerate subgraphs

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