Degree-constrained 2-partitions of graphs

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