Degree-constrained 2-partitions of graphs

A (δ≥k₁,δ≥k₂)-partition of a graph G is a vertex-partition (V₁,V₂) 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₁,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 NP-complete for the class of graphs of minimum degree less than g(k₁,k₂) and polynomial time solvable for all graphs with minimum degree at least g(k₁,k₂). 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.