Degree-constrained 2-partitions of graphs

2018/01/18 by Bang-Jensen, Joergen, Bessy, Stéphane
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1801.06216

Abstract

A (δ≥ k₁,δ≥ k₂)-partition of a graph G is a vertex-partition (V₁,V₂) of G satisfying that δ(G[V_i])≥ k_i for i=1,2. We determine, for all positive integers k₁,k₂, the complexity of deciding whether a given graph has a (δ≥ k₁,δ≥ k₂)-partition. We also address the problem of finding a function g(k₁,k₂) such that the (δ≥ k₁,δ≥ k₂)-partition problem is \cal NP-complete for the class of graphs of minimum degree less than g(k₁,k₂) and polynomial for all graphs with minimum degree at least g(k₁,k₂). We prove that g(1,k)=k for k≥ 3, that g(2,2)=3 and that g(2,3), if it exists, has value 4 or 5.

Related

• New Invariants for Partitioning a Graph into 2-connected Subgraphs
• Partitioning graphs with linear minimum degree
• Partitioning and coloring with degree constraints
• Complexity results on locally-balanced 2-partitions of graphs
• Tree-Partitions with Small Bounded Degree Trees