Partitioning a graph into degenerate subgraphs

DOI10.1016/J.EJC.2019.103015zbMATH Open1428.05241arXiv1803.04388OpenAlexW2972128333MaRDI QIDQ2011133FDOQ2011133

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)

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.

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

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

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)

Cites Work

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

Cited In (11)

• Vertex partition of hypergraphs and maximum degenerate subhypergraphs
• Digraphs and variable degeneracy
• A Catlin-type theorem for graph partitioning avoiding prescribed subgraphs
• 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
• Title not available (Why is that?)
• Vertex partitions and maximum degenerate subgraphs

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)